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

1345 — D Educational Codeforces Round 87 (Rated for Div. 2), problem: (D) Multiset
Автор kernelpanic77, история, 5 лет назад, По-английски

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

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

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

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.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить