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

Автор Akhmadzhanov, история, 7 месяцев назад, По-английски

Today I wanted to solve this problem: Heavy Intervals But I got TLE3 code: 260013398. that's why I changed the code a little bit and my code(260014069) was correct. But I don't understand how? Can you explain?

Here are the differences between my first and second codes

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

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

b.upperbound takes $$$O(logn)$$$ while upperbound(all(b), a[i]) takes $$$O(n)$$$ time.

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

for sets , b.upper_bound is O(log(n)) but upper_bound(all(b)) is O(n)

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

Using set.upper_bound() is O(log n), while std::upper_bound(set.begin(), set.end(), value) adds O(n) complexity due to linear search, potentially causing time limit.