kernelpanic77's blog

1345 — D Educational Codeforces Round 87 (Rated for Div. 2), problem: (D) Multiset
By kernelpanic77, history, 4 years ago, In English

Guys my code is continuously getting TLE on Test case 6. Can someone pls help find the bug? link to my code : https://mirror.codeforces.com/contest/1354/submission/80872965

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

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this is due to the fact that maybe the time complexity of your code is nlog^2q. Question requires it to be nlogq.

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

Try using fast i/o. I have also used similar approach and just using fast i/o might do it.

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

    I tried same approach with segment trees and it failed :(

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

      Yes, fenwick tree/BIT is faster than segment tree due to segment tree operations having larger constant factor. This question does have n,q = 1e6, and even BIT passes with around ~ 1s.

      → Reply