DO_NOT_MISS_IT's blog

Very weak test case in problem F of last Div. 4 round 849?
By DO_NOT_MISS_IT, history, 23 months ago, In English

Here is my accepted code : https://codeforces.net/contest/1791/submission/192106557

But this code should give TLE if the input is like :

1

200000 200000

a1 , a2 , a3 …… a200000

1 2 200000 (Update index 2 to 200000 and all 200000 queries are like this)

  • Vote: I like it
  • -11
  • Vote: I do not like it

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

Your submission will likely fail after retesting. Although the original test set was weak, a few good test cases which eliminate most of the $$$\mathcal{O}(nq)$$$ solutions have been added during the hacking phase.

→ Reply
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    My original solution was with segment tree + lazy and that got accepted. Later I tried this and was surprised when this brute force got passed. Yeah I will be happy if this fails in the system test, but this is a very common way to solve this problem and there should be a test case in the main test in which this code should fail.

    → Reply