need help in spoj problem on segment tree GSS1



Can someone help me with this [problem][1] from spoj. I am getting wrong answer on TC9 .
Here is my

[2] . I am using long long int and fast I/O but still getting WA.
Thanks in advance:)



Your code is all right except that struct g.

In struct g everything should be -infinty (or MIN, a number less than MIN(a*))

For example, consider an array with all elements as negative, and node such that

. (mid, end) is completely out of range (l, r)

. (start, mid) exactly (or partially) overlaps with (l, r)

Then in your merging t.sufsum=max(p2.sufsum,p2.sum+p1.sufsum); which means t.sufsum = 0; which is not the case as it’s < 0:

You can have a look at my code (though it’s almost similar to yours)


Thanks man this helped me a lot wasted about 4 hours. Finally AC