Question link : http://www.spoj.com/problems/OLOLO/
Answer link : http://ideone.com/FDClmr
I am Getting TLE in a O(nlg(n)) submission even after using fast I/O.
Can’t figure out the problem.
PS : I know approach of using xor , just want to know why i am getting TLE in this code.
EDIT :
cant understand why this approach works
while this shows TLE
while complexity of both is same
hey time complexity of your code is O(nlog(n)) not O(n).map takes log n time for every operation.
OHH my bad !!
Btw here N is 5*10^5 .
so how can we see before implementing our approach whether it will pass when complexity is given in terms of points(.134 sec here).
this question can be done using xor but an nlogn solution also gets an AC check my one here just used vectors + sort. Finding an item is generally easier in vectors as the memory is alloted contiguously which is not the case with map.And as maps are implemented as BSTs so they come with a little overhead so maybe you are getting TLE bcoz of this. But i think your answer should give an WA bcoz the input size can be upto 10^9 and in your program you are only using int everywhere.
yes time limits on spoj confuses you thats why i dont look at them often
why does this sorting based approach work while time complexity of sorting based and my map based is O(n*lg(n))???
@chunky_2808 this can be explained by the fact that sorting is a simple procedure and it is done at the beginning of the algorithm and rest of the algorithm works in linear time.on the other hand you are using a complex data structure during the whole algorithm.
For a bit more detailed analysis read the edited answer and as mentioned by @hruday968 using complex ds can increase your runtime quite significantly
OK thanks !!!
element of arr is of size 10^9 and range of int is -2,147,483,648 to 2,147,483,647 . That is the reason it is giving TLE and not WA.
Got AC using unodered_map!!
so u have taken 64 bit int i mistook it for 32 bit