ravi_sumit33's blog

TLE when using set

By ravi_sumit33, history, 5 years ago, In English

Hello Codeforces!

I was solving this problem and came up with an approach using set. I made submission but got TLE. If I am correct, time complexity of this submission is nlogn as total number of insert/erase operations in set is O(n) and logn for each upper_bound.

I know this approach is not the best one but considering constraints given in the problem, this should get an AC.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Try replacing upper_bound(all(st0), p) with st0.upper_bound(p).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    After this modification the code still TLEs, but this time on Test Case 11 instead of Test Case 10. I'm curious though, why did this change make the code faster?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I used sync_with_stdio(false); cin.tie(nullptr) and it got AC.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Thanks dorijanlendvaj as my solution got AC. As I understood, using upper_bound requires iterators to be incremented randomly which is O(n) in sets. But set.upper_bound does increment iterators by 1 and uses BST like search so is logn.

    → Reply