Can someone help me debug my Segment Tree(lazy propagation)?

general
, , ,
1

Hi!

I’ve been trying to solve this problem from CF lately: Circular RMQ

I implemented a Segment Tree and used lazy propogation for solving this problem. But two different implementations I’ve made both fail on the 5th case. The 1st one failed to correctly answer the 30th query, the second, even though answers the 30th query correctly(local manual testing) doesn’t answer the 25th query correctly.

My code is here. Does anyone know how I can debug such a data structure easily, as all test cases(small ones) seem to get answered correctly. Any clues/ideas would be appreciated.

Thanks and regards!

NibNalin

2

Try negative values for the array, in particular -1 (they are within the constraints).

It’s a bad bad idea to have a valid value as a signal for an empty segment.

1 Like
3

Hello, thans for looking into this, but this doesn’t seem to resolve the issue, even though your point is entirely valid: http://codeforces.com/contest/52/submission/12721828