im_mortal79's blog

Getting TLE for using upper_bound in BOX FITTING.
By im_mortal79, history, 5 years ago, In English

In the problem B of recent codeforces contest. I am using function upper_bound whose complexity is logn,but is still getting TLE see this 111426754 but after some minute changes in the code it got accepted see this 111426808 Now,I am not able to understand what is the difference in above codes. Please help me undestand.

Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

std::set and std::multiset have bidirectional iterators that's why std::lower_bound and std::upper_bound work much slowly than set::lower_bound or set::upper_bound (same for multiset). In general, if a container has a function that is already present in namespace std, use that function because there's a reason why it's there.

→ Reply
»
5 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

from https://stackoverflow.com/questions/64536493/difference-between-set-upper-bound-and-upper-boundset-begin-set-end-stl

set::upper_bound will use the set's capability to search for value efficiently (logarithmic with regards to the size of the container).

For std::upper_bound, using non-LegacyRandomAccessIterators, like a std::sets iterators (that are LegacyBidirectionalIterators), the number of iterator increments is linear.

→ Reply
»
5 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Check the following update to your solution.

111432310

→ Reply