Hi, I am trying to solve this problem from ACM ACPC 2017 — Array Queries contest using segment tree + lazy propagation but always gets wrong answer no matter what. Am I missing something or is my approach wrong ?
Here is my code: https://ideone.com/3s2FQk
Additionally, I think that the way in which you make propagation is wrong, but if you fix those things probably you get TLE, because the first operation is in the worst case O(N)
Why bother with segment trees? There is a simple O(N3log2(N)) solution using Adolf's Red-Black-Yellow tree.