Deleted by author 06.10.2011 15:39

Edited by author 06.10.2011 15:40

My idea:
There are 2 arrays: peoples[] and index[]. First with "quicksort" I sorted peoples[] and use "binary search". Then with AntiQuickSort I changed the array, as it appears before the first sorting and I've got TLE? Why? I don't found my misteke and I hope that you will help me!!

Anybody tell me your algo!!!!!!!!!!!

Let's count the complexity of your algo.
As I see: NlogN(sorting)+NlogN(antiqsort)+logN(to find any occurrence of people) + N/2(to find suitable number that matches a segment)= (2N+1)logN+N/2. It's only for one query. So, in total it will be N((2N+1)logN+N/2).
It's too slow.

Try to sort once and answer for each query using binary search.

Edited by author 05.10.2011 23:01

Thank you Ramil! You say that I should try to sort once, but how? I have three days could not decide!

Edited by author 06.10.2011 10:56