PaneerMakhani's blog

Trying to figure out why my solution gave TLE.
By PaneerMakhani, history, 2 days ago, In English

Hello Codeforces, I participated in contest and i wrote a solution which seems like O(nlogn) to me but I still got TLE despite of constraints for N being 10^6. Can anyone Help me figure out why I got TLE and how can I fix it. Submission Link :

Submission

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

»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

It is because of multiset, read this blog https://mirror.codeforces.com/blog/entry/122960

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

    But i haven't used count in my solution :(

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

      Btw i am the same person this is my alt account :D

      → Reply
»
2 days ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The bounds for this problem were a little too tight I am assuming, which led to the constant factor in time complexities also play a role, I had made an O(nlogn) submission without including

ios_base::sync_with_stdio(false); cin.tie(nullptr);

and it didn't pass, but after including this block guess what, it did.

Normally this should not be a factor but due to the tight bounds it did for some reason

I had also tried an O(n) solution, but without the 2 lines mentioned above and it still didn't pass

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Use fast IO for cin/cout or, use Scanf/Printf.

→ Reply