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 asked 18 Aug '15, 18:50

You may have a look at my friend's solution. https://www.codechef.com/viewsolution/7698077 answered 18 Aug '15, 19:47

The main reason you are getting TLE is because your are trying to set 10^7 size array to 0 for every test case. 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: 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 :) answered 18 Aug '15, 20:49
