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.
Yeah I got a TLE bc of this today
RIP. I guess you'll be more careful now
Wait, upper_bound() exists? I only learnt the latter form. What is the first function useful for?
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)
Yeah, but because it is slow you can do Binary Search on your own
How to convert a discussion on the SOI group to contribution!
I guess. Also a lot of people in comments were getting TLEs so yeah