Блог пользователя crozzhtt

question
Автор crozzhtt, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить