Hello codeforces community,
I tried the following solution in this problem and got TLE for the subtask2. For each union operation i tried to merge smaller size set into bigger size set and added element to the corresponding balanced bst. so for each union operation i will be taking time O((number of element in smaller size set) * (log(element in the bigger size set)) and find the kth element in O(log(size of given set)). what is the worst case complexity of this solution ? I think it is O(N*log^2(N)) amortized. O(N*log^2(N)) was it unacceptable ? Please help me.
Auto comment: topic has been updated by NeverSayNever (previous revision, new revision, compare).
Yes, I think it is O(Nlog2N). Another way to analyse the complexity is: for each individual element, say x, we will inserting x into a Balanced BST(BBST) at most O(logN) times, because when we merge smaller BBST with larger BBST, the size of the BBST grows by at least double and eventually the size could be at most N.
And queries are O(logN) worst case, so I think it should have passed. BTW, I can't see your solution, its not public. Probably your implementation has a higher constant.
Thank you so much for your reply. Let me paste my code on ideone so that you can have a look at it.
http://ideone.com/DKQVbo