You are viewing a single comment's thread. Return to all comments →
Agree. Although I used segmented tree, it was no need to know max on each step.
Amansbhandari in fact used dirac delta and theta functions instead.
Does using segment tree worked?
Did you get all AC?
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.
Just noticed your comment. I came to the same conclusion here