You are viewing a single comment's thread. Return to all comments →
I usedlazy propogation , worked fine.
I too tried Lazy Propagation but got segmentation fault after 6 test cases, even the Question Setter in the editorial says that Lazy Propagation can not pass all test cases. Please show the code you wrote which passed all the test cases.
I got AC using Segment tree with lazy propagation. http://ideone.com/DzZlW7. Just keep on updating the tree, and at each node store the maximum of its left and right child. And after all the k updates, apply Range maximum query.