I used segment tree with lazy propagation on problem WOUT but still got tle for 2nd subtask. Why?

This is link to my solution…please suggest any modification

I used segment tree with lazy propagation on problem WOUT but still got tle for 2nd subtask. Why?

This is link to my solution…please suggest any modification

The main reason you are getting TLE is because your are trying to set 10^7 size array to 0 for every test case.

10^7 * 10^3 = 10^10 (TLE).

Also your lazy propagation seems to be slow…I tried replacing your memset with update tree calls and yet a few cases gave TLE.

I am not sure how you can solve it with segment tree in the given time limit but you can try my solution.

link

My Algo is as follows:

Let a be the no. of l values <= i

Let b be the no.of h values < i

No of blocks to remove in that row = N - a + b

Then you can sum up all H consecutive row ans and find the minimum in O(N)

Note:I sorted l,h values so over all complexity is O(NLogN), but you can use counting sort to do it in O(N).

Hope this helps

You used memset to set two arrays each of length 10^7.

Also the test cases limit was 1000.

Considering you have 100 test cases only,memset would take >3s on ideone.

Here check it out-link