fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. struct node {
  5.     ll sum,presum,sufsum,maxsum;
  6. };
  7. vector<node>segtree(1000002);
  8. void build(vector<ll>v,ll low, ll high, ll pos){
  9.     if(low>high)return;
  10.     if(low==high){
  11.         segtree[pos].sum=v[low];
  12.         segtree[pos].presum=v[low];
  13.         segtree[pos].sufsum=v[low];
  14.         segtree[pos].maxsum=v[low];
  15.         return;
  16.     }
  17.     ll mid= (low+high)/2;
  18.     build(v,low,mid,2*pos+1);
  19.     build(v,mid+1,high,2*pos+2);
  20.     segtree[pos].sum=segtree[2*pos+1].sum+segtree[2*pos+2].sum;
  21.     segtree[pos].presum=max(segtree[2*pos+1].presum, segtree[2*pos+1].sum+segtree[2*pos+2].presum);
  22.     segtree[pos].sufsum=max(segtree[2*pos+2].sufsum,segtree[2*pos+2].sum+segtree[2*pos+1].sufsum);
  23.     segtree[pos].maxsum=max(segtree[pos].sufsum,
  24.                         max(segtree[pos].presum,
  25.                         max(segtree[2*pos+1].sufsum+segtree[2*pos+2].presum,
  26.                         max(segtree[2*pos+1].maxsum,segtree[2*pos+2].maxsum))));
  27.  
  28.  
  29. }
  30. node query(ll ql , ll qh, ll low , ll high, ll pos){
  31.     node result;
  32.     result.sum=result.presum=result.sufsum=result.maxsum=INT_MIN;
  33.     if(ql>high || qh<low || low>high)return result;
  34.     if(low>=ql && high<=qh)return segtree[pos];
  35.  
  36.     ll mid=(low+high)/2;
  37.  
  38.     if (ql > mid) 
  39.         return query(ql,qh,mid+1,high,2*pos+2);  
  40.     if (qh <= mid) 
  41.         return query(ql,qh,low,mid,2*pos+1); 
  42.  
  43.     node left=query(ql,qh,low,mid,2*pos+1);
  44.  
  45.     node right=query(ql,qh,mid+1,high,2*pos+2);
  46.  
  47.     result.sum=left.sum+right.sum;
  48.  
  49.     result.presum=max(left.presum, left.sum+right.presum);
  50.     result.sufsum=max(right.sufsum,right.sum+left.sufsum);
  51.     result.maxsum=max(result.sufsum,
  52.                         max(result.presum,
  53.                         max(left.sufsum+right.presum,
  54.                         max(left.maxsum,right.maxsum))));
  55.     return result;
  56.  
  57. }
  58. int main(){
  59.     ios_base::sync_with_stdio(false);
  60.     cin.tie(NULL);
  61.     ll n,i,q,j;
  62.     cin>>n;
  63.     vector<ll>v(n);
  64.     for(i=0;i<n;i++)cin>>v[i];
  65.     build(v,0,n-1,0);
  66.     cin>>q;
  67.     for(ll k1=0;k1<q;k1++){
  68.         ll ql,qh;
  69.         cin>>ql>>qh;
  70.         node result=query(ql-1,qh-1,0,n-1,0);
  71.        cout<< result.maxsum;
  72.        if(k1!=q-1)cout<<"\n";
  73.     }
  74.  
  75. }
Success #stdin #stdout 0.01s 34424KB
comments (?)
stdin
copy 
3
-1 2 3
3
1 2
1 3
2 3
stdout
copy 
2
5
5
https://ideone.com/vI4adT
problem GSS1, based on SPOJ submission 25784196 (CPP14), 2020-04-16 22:05:38
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!