need help in spoj problem on segment tree GSS1

general
, ,
1

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:)


  [1]: http://www.spoj.com/problems/GSS1/
  [2]: https://ideone.com/NDE3VZ
2

Your code is all right except that struct g.

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

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)

1 Like
3

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