fakeac's blog

Need Help in optimizing my code from Div-2 D Problem round #388
By fakeac, history, 8 years ago, In English

Here is my code for this problem — http://codeforces.com/contest/749/problem/D from Div-2 D round #388 Here is my submission --> http://codeforces.com/contest/749/submission/23178341 My code is well commented and as per the editorial given. It is taking too much time. The complexity is O(nlog(n)). How do I optimize my code? What operation/operations are taking too long ? Please Help! Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Dont insert every person and his bid into the set. Only insert the id of the person and his MAX bid in the set.
Now when removing people, you only have to remove a single element per unique id.
If the resultant set size=0 or 1, you have your answer.
If there are more than 1 elements in the set, find the 2nd maximum bid in the set and now binary search through the list of the maximal bid person and find a value which is just greater than the 2nd maximum bid.

Here is a code for reference-23165182

→ Reply