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

Автор YogeshZT, история, 2 года назад, По-английски

I was doing the question 1498B - Box Fitting. Here are my two submissions 271307925 and 271307851. One of the approaches works correctly while other gives TLE. The only difference between them is how I initialize the iterator 'it' using the upper_bound function.

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

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

If I am not mistaken, the TLE approach is looking for an upper bound of x in the block of memory delimited by $$$[m.begin, m,end()) $$$, while the AC code actually makes use of multiset::iterator to find the answers.

The TLE approach may work with vectors, but be careful when using it with other data structures.

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

What i have found is that multiset.upper_bound() is faster than upper_bound(multiset.begin(),multiset.end()) and the reason attributed is the fact that multiset.upper_bound is optimized to take advantage of the internal structure of a multiset, which is typically implemented as a balanced binary search tree (e.g., a Red-Black Tree). The member function can directly leverage the tree's properties to perform the lookup efficiently as compared to the general upper_bound function which is from algorithm header file and it is not designed to take advantage of the properties of multiset , which the member upper_bound function does.

You can check this out too if you want : https://stackoverflow.com/questions/64536493/difference-between-set-upper-bound-and-upper-boundset-begin-set-end-stl

Sorry if there is any grammatical error.

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

lower_bound(b.begin(), b,end(), val) is $$$O(n)$$$,

while b.lower_bound(val) is $$$(\log n)$$$