SPOJ GSS 1 Wrong Answer

SPOJ problem GSS1, find the problem here

How to exactly make the query?

I have stored best, lsum, rsum and total sum in each node of segment tree.

Code should be helpful.

Thanks in advance. :slight_smile:


Your method of query is not corerct

Have a look at it.

1 Like

Just think about this line - return max(query(qlo, qhi, lo, mid, 2*pos+1), query(qlo, qhi, mid+1, hi, 2*pos+2));

Is this always true?

consider this test case :
1 -2 3 4 -1 6
1 3
2 6
1 6
4 6
5 6
3 5


As @shukrant said always returning max of left and right subtree is not correct.

A hint : It has something to do with the lsum and rsum variable of your code.

BTW Your code was really clean and easy to understand.


1 Like

If you need more help I can give you my code, but trying yourself first would be better I guess :smiley:

1 Like