fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define mod 1000000007ll
  5.  
  6. struct node
  7. {
  8.     ll mx;
  9.     ll tsum;
  10.     ll psum;
  11.     ll ssum;
  12. };
  13.  
  14. void build(node tree[],ll arr[],ll ss,ll se,ll idx)
  15. {
  16.     if(ss==se)
  17.     {
  18.         tree[idx].mx = arr[ss];
  19.         tree[idx].tsum = arr[ss];
  20.         tree[idx].psum = arr[ss];
  21.         tree[idx].ssum = arr[ss];
  22.         return;
  23.     }
  24.     ll m = (ss+se)/2;
  25.     build(tree,arr,ss,m,2*idx+1);
  26.     build(tree,arr,m+1,se,2*idx+2);
  27.  
  28.     struct node left = tree[2*idx+1];
  29.     struct node right = tree[2*idx+2];
  30.     tree[idx].psum = max(left.psum,right.psum+left.tsum);
  31.     tree[idx].ssum = max(right.ssum,left.ssum+right.tsum);
  32.     tree[idx].tsum = left.tsum+right.tsum;
  33.     tree[idx].mx = max((left.ssum+right.psum),max(left.mx,right.mx));
  34.  
  35. }
  36.  
  37. node query(node tree[],ll ss,ll se,ll qs,ll qe,ll idx)
  38. {
  39.     // cout<<ss<<" "<<se;
  40.     if(qs<=ss && qe>=se)
  41.     {
  42.         return tree[idx];
  43.     }
  44.     else if(qs>se || qe<ss)
  45.     {
  46.         struct node waste;
  47.         waste.mx = waste.tsum = waste.psum = waste.ssum = -5000000ll;
  48.         return waste;
  49.     }
  50.  
  51.     ll m = (ss+se)/2;
  52.     struct node left = query(tree,ss,m,qs,qe,2*idx+1);
  53.     struct node right = query(tree,m+1,se,qs,qe,2*idx+2);
  54.     struct node retval;
  55.     retval.psum = max(left.psum,right.psum+left.tsum);
  56.     retval.ssum = max(right.ssum,left.ssum+right.tsum);
  57.     retval.tsum = left.tsum+right.tsum;
  58.     retval.mx = max((left.ssum+right.psum),max(left.mx,right.mx));
  59.     return retval;
  60. }
  61.  
  62. int main()
  63. {
  64.  
  65.     ios::sync_with_stdio(0);
  66.     cin.tie(NULL); cout.tie(NULL);
  67.     #ifndef ONLINE_JUDGE
  68.     freopen("input.txt", "r", stdin);
  69.     freopen("output.txt", "w", stdout);
  70.     #endif
  71.  
  72.     ll n;
  73.     cin>>n;
  74.     ll arr[n];
  75.  
  76.     for(int i=0; i<n; i++)
  77.         cin>>arr[i];
  78.  
  79.     struct node tree[4*n+1];
  80.  
  81.     for(ll i=0; i<4*n+1; i++)
  82.     {
  83.         tree[i].mx = -5000000ll;
  84.         tree[i].tsum = -5000000ll;
  85.         tree[i].psum = -5000000ll;
  86.         tree[i].ssum = -5000000ll;        
  87.     }
  88.     build(tree,arr,0,n-1,1);
  89.     // for(ll i=1; i<4*n+1; i++)
  90.     // {
  91.     //     cout<<tree[i].mx<<" "<<tree[i].tsum<<" "<<tree[i].psum<<" "<<tree[i].ssum<<endl;
  92.     // }
  93.  
  94.     ll q, l, r;
  95.     cin>>q;
  96.     while(q--)
  97.     {
  98.         cin>>l;
  99.         cin>>r;
  100.         l--;
  101.         r--;
  102.         struct node ans = query(tree,0,n-1,l,r,1);
  103.         cout<<ans.mx<<endl;
  104.     }
  105.  
  106.  
  107.  
  108.     return 0;
  109. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/xEHpob
problem GSS1, based on SPOJ submission 25628293 (CPP14), 2020-03-26 07:56:08
language:
C++14 (gcc 8.3)
created:
5 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!