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

Why time limited exeeded in my O(nlogn) solution
Автор proAakash, история, 3 месяца назад, По-английски

i was trying to solve this problem:- https://mirror.codeforces.com/contest/1801/problem/B

My solution :- https://mirror.codeforces.com/contest/1801/submission/278323418

In my solution i wrote a O(nlogn) solution and the judge is showing time limit exceeded. But in editorial the solution given is O(nlogn) and that is getting passed. I am having trouble understanding how this is happening.

plzz help :,(

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

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

Auto comment: topic has been updated by proAakash (previous revision, new revision, compare).

→ Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

set has its own object function lower_bound to use. Do not use lower_bound in algorithm.h, as performing it on set would most of the time cause an $$$\mathcal{O}(n)$$$ time complexity per call.

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

    Resubmitted but WA: 278326222. Well, since I didn't solve this one yet, I wouldn't give further advice, but at least the TLE is dealt with.

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

    why lower_bound that isn't method in set object act in o(n)

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

      Please refer to this:

      However, if ForwardIt is not a LegacyRandomAccessIterator, the number of iterator increments is linear in $$$N$$$.

      Notably, std::map, std::multimap, std::set, and std::multiset iterators are not random access, and so their member lower_bound functions should be preferred.

      → Ответить
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cuz your sol is not O(nlogn), dummy.

→ Ответить