Help Needed on TRIQRY from APRIL LTIME 2020

Can anybody help why I am getting TLE in subtask 1 for the problem https://www.codechef.com/LTIME83B/problems/TRIQRY?

My solution:
https://www.codechef.com/viewsolution/33076168

memset(BIT, 0, sizeof BIT); and T\le 100.
Do you see a problem?

Can you explain a bit more?

@everule1 What do you mean? I do not see a problem in this line.

Size of BIT is 2*10^6, so doing that 100 times will make you waste 0.5 seconds. Why not do 2*n*sizeof(int) to save time.

After some optimization Subtask 2 took 0.61 sec. I don’t think that line is the issue. Even if I comment that line I am getting TLE for Subtask 1. The surprising part is it passes Subtask 2 but not Subtask 1 which has MAXN = 10^5.

Updated: https://www.codechef.com/viewsolution/33178359

It is possible you may pass the value 0 to idx in update. That is causing the TLE.

1 Like