Abito's blog

Use proper upper_bound()
By Abito, history, 16 months ago, In English

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.

  • Vote: I like it
  • +36
  • Vote: I do not like it

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah I got a TLE bc of this today

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

    RIP. I guess you'll be more careful now

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply