In this contest, while I was browsing through FST submissions, I encountered many TLEs on test 8 in B. Here are some examples: 142848311, 142836654. The solutions appeared to be completely correct. What happened here?
The problem was that these contestants used
memset before every test. If you didn't know,
memset(a, 0, sizeof(a)) is linear in the size of the array
This is why these contestant TLEd. Every testcase, they did $$$1000000$$$ unnecessary operations.
The lesson here? Stop using
memset to reset stuff when there are many testcases. Resetting by hand works just fine. Or know how
memset actually works, so that you don't TLE.