@ramini For each block, we use a map maintaining the frequency of all (distinct) elements in that block.
we don’t have multiset in java any suggestion for this case
@ayush201 You could use a Map and store the count of each element. It should have the same complexity.
1 Like
Hey misha, I edited your answer a little to give some formats (Decent formatting + Decent explanation= Profit 
). Please have a look in case you find concern. 
2 Likes
@prince367 The A[i]'s are the keys of the maps. The way data is stored in maps is different. If I insert 10^9 into the map, it goes to the first instead of the 10^9 th position as it would do for arrays.
You’re welcome 
1 Like
Btw, if you’ll use X-fast trie - Wikipedia you can update your solution theoretically to O(Q sqrt (N log log N)), I don’t how it goes practically, next and previous elements can be found in time O(log log N), but insert/erase in O(log N)
4 Likes
Done. Please have a look and verify
1 Like
@bazsi700 - CodeChef: Practical coding for everyone i have implemented similar approach here, but it is timing out can you have a look why?
@divyansh_gaba7 The problem is you use std::lower_bound in query, which is O(N) on sets. You should use std::set::lower_bound which runs O(\log{N}), thus replace lower_bound(t[l].begin(),t[l].end(),m) by t[l].lower_bound(m).
I faced the same problem once, and posted a blog about it on CF, where I got explanation for it:
Probably the problem is with double precision. However you don’t need to precalculate the division into a double, because you can perform standard division each time which takes floor operation anyways.
@bazsi700 , when I change the datatype to double, it is passing 1st test case but when I change it to long double it is passing only 2nd test case, why?(isn’t first test case a sub set of 2nd) I just want to know what’s happening behind…
No, Rating are updated only upto November Cook Off.
@vipin_bhardwaj To avoid double precision issues. The sum of A_L and A_R may be odd, this is why we need double, but double can have precision issues, so you can’t use = sign on doubles.
E.g. if you have this code:
double x = 2;
x = (x*5)/2;
then probably x == 5 expression will be false, because x will be something like 4.999999 or 5.0000001.
That’s why you should always compare doubles with an error, which I chose 0.01.
1 Like