crozzhtt's blog

question
By crozzhtt, history, 4 years ago, In English

hello everybody! i have a question for problem 1536D-Omkar and Medians:https://mirror.codeforces.com/problemset/problem/1536/D I had seen the tutorial for this problem , and i saw some AC submissions. But i don't know why my code is TLE at tc 11.
This is my code: https://ideone.com/xiRkKG?fbclid=IwAR0BJSaiFqvN3smJg7ZASnla8Y3CZzxmk-vjFRHVw-fVqHd06ypAiYp4180 Thanks for your answer!

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The way you take upper bound is wrong. Here is the corrected code https://mirror.codeforces.com/contest/1536/submission/119202465 . Set has its own inbuilt upper bound function whose complexity is O(logn). Using the generic upper_bound on set will give O(n) worst case complexity.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I think it's worth explaining why that's the case.

    lower_bound/upper_bound is only $$$O(\log n)$$$ for Random-Access Iterators. If you think about how it works, it jumps around the container to search for the element, but if it can't jump very fast (like in a set, because you can only do it++ or it--), then just moving to the positions will take $$$O(n)$$$ (in total). That's why map and set have specialized lower/upper _bound functions.

    → Reply