i think the intended solution for this problem is O(n lg^2(n))
i used fenwick tree and two multi sets in each node to represent the number of additions and deletion of each number in the input data. i think the complexity of this solution is O(n lg^2(n)) which is pretty much acceptable by problem constrains. however, this solution gets TL on test #11
after seeing other fenwick tree based solutions i noticed that the difference is using one map instead of two multi sets. i rewrote the code and indeed it was accepted!
can anybody help me with this issue. i don't know where i have gone wrong. switching set to map reduced a TL to a 420 ms AC solution. any help would be appreciated.
btw, what's the problem with codeforces judging system. it seems to be significantly slow.
The count function is linear in the value it returns which means that if it returns N, then its complexity is O(N).
new thing to learn, thank you
tbh codeforces judging system is quite fast in my opinion (If you consider SPOJ's...)
it seems like a lot of submissions get stuffed in the queue. see the status this is unusual for codeforces. yesterday about 7 pages of submissions were showing "In queue".
You're not alone. I'm experiencing the same problem for quite a long time now. Testing one submission can take up to 20 minutes.