(EDITED) TLE in OLOLO - Onotole needs your help

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.

2 Likes

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.

1 Like

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.

1 Like

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