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

Use proper upper_bound()
Автор Abito, история, 16 месяцев назад, По-английски

Many people use the normal upper_bound() function, which is slow (at worst case O(n)) and get TLE. When you are using a set/multiset/map, use containername.upper_bound() This function uses Binary Search which runs at O(logn) time. Please be careful next time. This is only a reminder because I'm seeing a lot of people get TLE because of this.

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

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

Yeah I got a TLE bc of this today

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

Wait, upper_bound() exists? I only learnt the latter form. What is the first function useful for?

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

    upper bound on literally any sorted thing other than set/map/multiset/multimap/linked list (does technically work on BBSTs/linked lists but they don't have random access iterators so distance() is $$$O(n)$$$ in that case)

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

      Yeah, but because it is slow you can do Binary Search on your own

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

How to convert a discussion on the SOI group to contribution!

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

    I guess. Also a lot of people in comments were getting TLEs so yeah

    → Ответить