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.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 4 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 8 | Dominater069 | 154 |
| 8 | nor | 154 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 14.11.2024 19:56:38 (j1).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by YogeshZT (previous revision, new revision, compare).
Auto comment: topic has been updated by YogeshZT (previous revision, new revision, compare).
Auto comment: topic has been updated by YogeshZT (previous revision, new revision, compare).
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.
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.
Thanks for the answer. So it means there might be more functions which have varied time complexities depending on whether we use them in a way which utilizes the advantage of the data structure we use them with?
most likely all the member function to particular data structures have been implemented in a way to leverage the specific properties of data structure to its use as compared to generic one.
lower_bound(b.begin(), b,end(), val) is $$$O(n)$$$,
while b.lower_bound(val) is $$$(\log n)$$$