[Help]Why am I getting WA for this spoj problem?

Here is the problem link -GSS1

Here’s my code. I wanted to know why am I getting WA ? I am solving this using segment tree method.

``````#include<bits/stdc++.h>
using namespace std;

#define size 50005

struct node{
int total , pre , suf , bst;

node(){
total = pre = suf = bst = 0;
}
node(int pos): total(pos) , pre(pos) , suf(pos) , bst(pos){
}
};

node tree[4*size];
int a[size];

node combine(node low , node high){
node tmp;
tmp.total = low.total + high.total;
tmp.bst = max(max(low.bst , high.bst) , low.suf + high.pre);
tmp.pre = max(low.pre , low.total + high.pre);
tmp.suf = max(high.suf , high.total + low.suf);
return tmp;
}

void build(int low , int high , int pos)
{
if(low == high){
tree[pos] = node(a[low]);
}
else
{
int mid = (low+high)>>1;
build(low , mid , pos<<1);
build(mid+1 , high , 1+pos<<1);

tree[pos] = combine(tree[pos<<1] , tree[1+pos<<1]);
}
}

node query(int qlow , int qhigh , int low , int high , int pos)
{
if(qlow == low && qhigh == high)return tree[pos];
int mid = (low+high)>>1;

if(qhigh <= mid)return query(qlow , qhigh , low , mid , pos<<1);
if(qlow > mid) return query(qlow , qhigh , mid+1 , high , 1+pos<<1);

node left = query(qlow , mid , low , mid , pos<<1);
node right = query(mid+1 , qhigh , mid+1 , high , 1+pos<<1);

return combine(left , right);

}

int main()
{
int n;cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
build(0 , n-1 , 1);
int q;cin>>q;
while(q--)
{
int a,b;cin>>a>>b;
node res = query(a-1 , b-1 , 0 , n-1 , 1);
cout<<res.bst<<endl;
}

return 0;
}``````

One approach that works whenever you get a WA is to generate some random test cases and compare your code’s output to the correct answer(which can be found by running those tests against a correct code).

For generating random tests this toolkit comes in handy.

For the correct output you can refer to this code .

Hope this helps.

3 Likes

Thanks , that tool is so useful.

Glad I could be of help!

1 Like

thanks @sarvagya for that kit… (y) !