GSS1

#Problem Link

Prerequisites:

1.  e-maxx

 

 

View Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mx = 50010;
ll a[mx];

struct data {
int sum, pref, suff, ans ;
}tree[4*mx] ;
data make_data ( ll val ) {
data res ;
res. sum = val ;
res. pref = res. suff = res. ans = val ;
return res ;
}
data combine ( data l, data r ) {
data res ;
res. sum = l. sum + r. sum ;
res. pref = max ( l. pref , l. sum + r. pref ) ;
res. suff = max ( r. suff , r. sum + l. suff ) ;
res. ans = max ( max ( l. ans , r. ans ) , l. suff + r. pref ) ;
return res ;
}

void build(ll node,ll b,ll e)
{
if(b==e)
{
tree[node]=make_data(a[b]);
}
else{
int mid=(b+e)/2;
build(node*2,b,mid);
build(node*2+1,mid+1,e);
tree[node]=combine(tree[node*2],tree[node*2+1]);
}
}
void buildsm(ll node,ll b,ll e)
{

}

ll update(ll node,ll b,ll e,ll x,ll y)
{

}

data query(ll node,ll b,ll e,ll l,ll r)
{
if(l==b &&e==r)
return tree[node];
int mid=(b+e)/2;
if(r<=mid) return query(node*2,b,mid,l,r); if(l>mid)
return query(node*2+1,mid+1,e,l,r);
return combine(query(node*2,b,mid,l,mid),query(node*2+1,mid+1,e,mid+1,r));
};
ll n,q;
int main()
{

scanf(“%lld”,&n);
memset(tree,0,sizeof tree);
memset(a,0,sizeof a);
for(ll i=1;i<=n;i++)
{scanf(“%lld”,&a[i]);
}
build(1,1,n);
//buildsum(1,1,n);
scanf(“%lld”,&q);
while(q–)
{
ll x,y;
scanf(“%lld %lld”,&x,&y);
{
printf(“%lld\n”,query(1,1,n,x,y).ans);
//cout<<query(1,1,n,x,y)<<endl;
}

}

}

 

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s