I have tried various test cases but still my test case 9 is giving wrong ans
Problem link:https://www.spoj.com/problems/GSS1/
My code:
//https://www.spoj.com/problems/GSS1/
#include
#include
using namespace std;
#define int long long
#define LLLONG_MIN INT_MIN
class Obj
{
public:
int ans;
int sum;
int suf;
int pre;
Obj(int a=0,int b=0,int c=0,int d=0)
{
ans=a;
sum=b;
suf=c;
pre=d;
}
};
int *tree;
int * prefix;
int *suffix;
int *total;
int * arr;
void buildTree(int s,int e,int index)
{
if(s==e)
{
tree[index]=prefix[index]=suffix[index]=total[index]=arr[s];
return;
}
int mid=(s+e)/2;
buildTree(s,mid,2*index);
buildTree(mid+1,e,2*index+1);
int left,right;
left=2*index;
right=2*index+1;
total[index]=total[left]+total[right];
prefix[index]=max(prefix[left],total[left]+prefix[right]);
suffix[index]=max(suffix[right],suffix[left]+total[right]);
tree[index]=max(tree[left],tree[right]);
tree[index]=max(tree[index],suffix[left]+prefix[right]);
}
Obj query(int s,int e,int qs,int qe,int index)
{
//if out of bounds
if(qe<s||qs>e)
{
return Obj(LLLONG_MIN,LLLONG_MIN,LLLONG_MIN,LLLONG_MIN);
}
//if complete overlap
if(qe>=e&&qs<=s)
return Obj(tree[index],total[index],suffix[index],prefix[index]);
int mid;
mid=(s+e)/2;
Obj left=query(s,mid,qs,qe,2*index);
Obj right=query(mid+1,e,qs,qe,2*index+1);
if(left.ans==LLLONG_MIN)return right;
else if(right.ans==LLLONG_MIN)return left;
Obj ob;
ob.sum=left.sum+right.sum;
ob.pre=max(right.pre,right.sum+left.pre);
ob.suf=max(left.suf,left.sum+right.suf);
ob.ans=max(right.ans,left.ans);
ob.ans=max(ob.ans,left.suf+right.pre);
return ob;
}
signed main()
{
int n;
cin>>n;
arr=new int [n+1];
for(int i=1;i<=n;i++)
cin>>arr[i];
tree=new int[4*n+1]{0};
prefix=new int[4*n+1]{0};
suffix=new int[4*n+1]{0};
total=new int[4*n+1]{0};
buildTree(1,n,1);
int q;
cin>>q;
while(q--)
{
int x,y;
cin>>x>>y;
Obj ob=query(1,n,x,y,1);
cout<<ob.ans<<"\n";
}
delete[]arr;
delete[]tree;
delete[]prefix;
delete[]suffix;
delete[]total;
return 0;
}