Akhmadzhanov's blog

What is the problem?
By Akhmadzhanov, history, 9 months ago, In English

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

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply