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

Help needed: A weird TLE.
Автор Number_72, история, 23 месяца назад, По-английски

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

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

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

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

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

    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.

    → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Spoiler
      → Ответить
    • »
      »
      »
      23 месяца назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

      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)$$$.

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

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

    → Ответить