CODECHEF LUNCH TIME PROBLEM

Revision en2, by NeverSayNever, 2015-06-28 14:00:08

Hello codeforces community,

problem link

mysolution link

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English NeverSayNever 2015-06-28 14:00:08 2 Tiny change: 'link</a>\n<a href=' -> 'link</a>\n\n<a href='
en1 English NeverSayNever 2015-06-28 13:59:41 748 Initial revision (published)