problem link :-SPOJ.com - Problem GSS1 why i m getting WA
enter code here
#include<iostream>
#include<cmath>
#include<utility>
#include<cstdio>
using namespace std;
int N=50000;
int M[1<<23][2];
int a[1<<23];
void initialize(int node,int i,int j)
{
if(i==j)
{
if(a[i]>0)
M[node][0]=a[i];
else
M[node][0]=0;
M[node][1]=a[i];
}
else
{
initialize(2*node,i,(i+j)/2);
initialize(2*node+1,(i+j)/2+1,j);
M[node][0]=M[2*node][0]+M[2*node+1][0];
M[node][1]=M[2*node][1]>M[2*node+1][1]?M[2*node][1]:M[2*node+1][1];
}
}
pair<int,int> query(int node,int b,int e,int i,int j)
{
pair<int,int> p1,p2;
if(i>e||j<b)
return make_pair(0,-15008);
if(b>=i&&e<=j)
return make_pair(M[node][0],M[node][1]);
p1=query(2*node,b,(b+e)/2,i,j);
p2=query(2*node+1,(b+e)/2+1,e,i,j);
return make_pair(p1.first+p2.first,max(p1.second,p2.second));
}
int main()
{
pair<int,int> AL;
int m,n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
initialize(1,0,n-1);
cin>>m;
int x,y;
while(m--)
{
cin>>x>>y;
AL=query(1,0,n-1,x-1,y-1);
if(AL.first==0)
cout<<AL.second<<endl;
else
cout<<AL.first<<endl;
}
}