WOUT(AUG15)

general
1

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

https://www.codechef.com/viewsolution/7746551

2

You may have a look at my friend’s solution. https://www.codechef.com/viewsolution/7698077

3

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 :slight_smile:

4

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