SPOJ ORDERSET TLE

I have used a TreeSet which is basically an in-built implementation of red-black tree
And its also given in its java documentation, that all add,remove operations take log(n) time
Then for the Kth and Count Queries ,i am converting the Treeset object into an array and doing a binary search over the array.
So basically all operations take just log(n) time.
So why TLE??
Also the ideone test case answer is correct…i have confirmed it from an accepted solution.

Well, isn’t converting a TreeSet into an Array an O(n) operation?

1 Like

Also, it would be nice if anyone can explain the segment tree and fenwick tree approach…

Ohh, i missed that. Thank you so much.
Can you explain the segment tree and fenwick tree approach?

First you normalise all numbers you find in the input, then you keep a segment tree on a 0-1 vector of every number’s apparencies. Three of the operations are trivial on this data structure, for the kth-order statistic you can either use binary search, for a total of O(log^2) per query, or think of a clever aproach which gives O(log) per query. Hope this helped.