Hi there, while working on this problem, I ran into a situation where using std::upper_bound(set) TLE'd, while replacing the set with a sorted array was comfortably within the time constraints. (TLE submission: 145179964, AC: 145179970). AFAIK, these two should be equivalent O(log n), up to constants. In practice, is it just that those constant factors are great enough to TLE solutions that are asymptotically within the constraint, or is there something else I'm missing when using std::upper_bound with sets instead of vectors?
Thanks!
That's probably incorrect. From the information I get, when applying to std::set, the time complexity of std::upper_bound will degenerate because it doesn't have random access iterator. Instead, member function upper_bound of std::set has a time complexity of $$$O(log\;n)$$$ and it might work with you solution.
No, std::upper_bound works with binary search approach in the sorted array (O(logN)) while in sets/maps doesn't iterate through Binary search (IDK the exact way), but it works in O(N) time.
Instead, you can use it this way.
set_name.lower_bound(value); it works in O(log N)
set::upper_bound