Can anyone help me to fix Tle in this code for the above problem. link . I used BIT and square root decomposition
problem is map:-)
unordered_map insertion takes constant time but map insertion takes logarithmic time.
also input methods should be faster use fast-io.
this is my TLE solution link:-https://www.codechef.com/viewsolution/12299117
i just switched to fast-io and unordered_map got ac:-
Thanks but I think there is some other problem. Can you comment on the complexity of ur code during the query part if all integers are distinct and K=N and queries are balanced. Wont completely iterating over map everytime cause tle…though my approach is a bit different
I m not familiar with your approach!!!
It doesnt matter if k==n in my approach because i m counting for every query the map’s value.
Time Complexity:- O(n*sqrt(n)):- for MO’s algorithm
O(1) :- for insertion i.e every new element encountered(because it is unordered_map)
O(n) for counting numbers that are greater than k…
Btw ur complexity of the code is O(P^2) where P is the total number of distinct numbers in the array and K is very large. anyways waiting for some one to help
I have tried same approach during the contest as yours. I also got TLE. The reason I got to know is because of extra log(N) factor. This log(N) is due to two things , one because of map and other because of Fenwick Tree (BIT). This map factor can be reduced to some sense by using unordered_map but factor introduced by BIT can not be decreased.
Solution : Now how to reduce the factor of BIT. Instead of BIT just use brute force approach of prefix sum array. Here prefixSum[i] = sum[i] + sum[i+1] + … + sum[N] .
So add method of our MO’s will be as follows :
void add(int x) int count = map[x]; decrease 1 in prefix Sum array from index i = 1 to count increase 1 in prefix Sum array from index i = 1 to (count + 1) map[x]++
However just notice decrease and increase lines just merges and reduces to following code :
void add(int x) int count = map[x]; prefixSum[count+1]++; map[x]++
Similarly for remove(x).
Thus log(N) factor of BIT is removed.
The map log(N) factor can be more better reduced by using co-ordinate compression.
So the reason why our earlier implementation was giving TLE because of extra log(N) factor induced by BIT.