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.
THANKS IN ADVANCE.
#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;
}