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

Getting TLE for using upper_bound in BOX FITTING.
Автор im_mortal79, история, 4 года назад, По-английски

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.

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

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

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.

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

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.

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Check the following update to your solution.

111432310

→ Ответить