Number_72's blog

Help needed: A weird TLE.
By Number_72, history, 2 years ago, In English

Hello Codeforces, yesterday I have submitted various solutions for problem C. Although I have estimated my time and memory complexity to be O(n log n) I was surprised to see that it gave time limit exceeded, can you help me? 188111812

Tags tle
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +30 Vote: I do not like it

std upper bound is linear on sets, use set::upper_bound instead

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh wow! That got AC. Why does this happen? Are there any other functions I need to be cautious when using? Thank you very much for your reply.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Spoiler
      → Reply
    • »
      »
      »
      2 years ago, # ^ |
      ← Rev. 2   Vote: I like it +20 Vote: I do not like it

      You called a general function std::upper_bound. The way this function works is: if it is called on random access iterator, such as std::vector<int>::iterator, a binary search is performed, achieving $$$O(\log n)$$$ (since it is possible to access any position in constant time). Otherwise, if the iterator is not random access (such as std::set<int>::iterator), std::upper_bould can't do any better than to just advance the iterator linearly to find the answer.

      On the other hand, std::set<int>::upper_boupd has access to the inner workings of set, which is a binary search tree, so it can go up and down the tree in a smart way to get the answer in $$$O(\log n)$$$.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    downvoted. upper blund is not the problem. optimization is the issue.

    → Reply