@pragrame I am still unable to solve the problem ORDERSET using BIT, Can you explain how to solve it using BIT?
Finally an accept. Stupid bug !! Nice problem, nice editorial 
Thanks, I cant figure out why in java I am getting RTE non-zero exit code …
I finally Understood how its being done and have implemented it successfully. Apparently the index of the BIT are the Time values and we increment those indexes in the BIT which corresponds to the time when we made the Set operations and also decrement those indexes in the BIT when the previous set operation was done.
1 Like
Could anyone explain the need to deleting elements from BIT?
Specifically this code -
if RS0TS[i] > RS1TS[i]
RS0.increment(RS0TS[i], -1); //delete the previously stored time-stamp of RS0TS[i]
else
RS1.increment(RS1TS[i], -1); //delete the previously stored time-stamp of RS1TS[i]Really a nice editorial.It would have been better if the setter’s and tester’s solution were written with comments.
@admin : the time limit is very tight with this as well because i got TLE with fast Input and cin but when i replaced cin with printf its AC.It would be better if you look at these issues because even if ones algorithm is correct its not good to get TLE just due to “cin” and “cout” or sometimes even with “scanf”. These never happen at codeforces or any other coding site
Can we have a array, data[2][N] where at each index in first row we store number of zeros in N rows, and in 2nd row, we store number of zeros in each column.
At each “Rowset/Colset i 1/0” operation we will change the counts accordingly.
While querying we just need to look up this array at correct indices.
Correct me if wrong.
@vivekvelankar : How do you update the counts with each operation ??? Suppose i do Rowset i 0 . Now one entry in each column has become 0 . So you have update N entries in your column . For Q queries , it will take , N * Q updates , Since N , Q < 2 * 10^5 . This is not acceptable . Also how do you know in this case which columns will have their count incremented and which not , as some entries may already be zero , while some may not .
What do you mean when you write “fast input and cin”? It’s written in FAQ, that
The second most common cause of TLE is that your method of reading input and writing output is too slow. In Java, do not use a Scanner; use a BufferedReader instead. In C++, do not use cin/cout - use scanf and printf instead.
1 Like
A “ColSet i x” operation will require you to update values of all data[0][i]. Thats O(N) right there.