fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long  ll;
  4. ll seg[200000][4];//sum,prefix,suffix,max
  5.  
  6. void build(ll seg[][4],ll low,ll high,ll pos,ll arr[])
  7. {
  8.     ll mid;
  9.     if(low==high)
  10.     {
  11.     seg[pos][0] = arr[low];//0 for sum
  12.     seg[pos][1] = arr[low];//1 for prefix
  13.     seg[pos][2] = arr[low];//2 for suffix
  14.     seg[pos][3] = arr[low];//3 for best
  15.     return;
  16.     }
  17.     else
  18.     {
  19.         mid = (low+high)/2;
  20.         build(seg,low,mid,(2*pos)+1,arr);
  21.         build(seg,mid+1,high,(2*pos)+2,arr);
  22.         seg[pos][0] = seg[(2*pos)+1][0] + seg[(2*pos)+2][0];
  23.         seg[pos][1] =  max(seg[(2*pos)+1][0]+ seg[(2*pos)+2][1],seg[(2*pos)+1][1]);
  24.         seg[pos][2] = max(seg[(2*pos)+2][0]+seg[(2*pos)+1][2],seg[(2*pos)+2][2]);
  25.         seg[pos][3] =  max ( max(seg[(2*pos)+1][3],seg[(2*pos)+2][3]),seg[(2*pos)+1][2]+seg[(2*pos)+2][1]);
  26.     return;}
  27. }
  28. ll query(ll seg[][4],ll low,ll high,ll qlow,ll qhigh,ll pos,ll arr[])
  29. {
  30.     if(qlow>high || qhigh<low)
  31.     {
  32.         return -150009;
  33.     }
  34.     else if(low>=qlow && high<=qhigh)
  35.     {
  36.         return seg[pos][3];
  37.     }
  38.     else
  39.     {
  40.     ll mid;
  41.     mid =(low+high)/2;
  42.     return (max(query(seg,low,mid,qlow,qhigh,(2*pos)+1,arr),query(seg,mid+1,high,qlow,qhigh,(2*pos)+2,arr)));
  43.  
  44.     }
  45. }
  46. int main()
  47. {
  48.    memset(seg,0,sizeof(seg));
  49.     ll a,b,c,d,e,f,g,h,i,j,k;
  50.     scanf("%lld",&a);
  51.     ll arr[a+1];
  52.     for(b=0;b<a;b++)
  53.         scanf("%lld",&arr[b]);
  54.     build(seg,0,a-1,0,arr);
  55.    // for(b=0;b<10;b++)
  56.      //   cout<<seg[b][0]<<" "<<seg[b][1]<<" "<<seg[b][2]<<" "<<seg[b][3]<<"\n";
  57.     //cout<<"\n";
  58.     scanf("%lld",&c);
  59.     for(d=0;d<c;d++)
  60.     {
  61.         scanf("%lld %lld",&e,&f);
  62.       ll po = query(seg,0,a-1,e-1,f-1,0,arr);
  63.       printf("%lld\n",po);
  64.     }
  65. }
  66.  
Success #stdin #stdout 0s 21488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-150009
-150009
https://ideone.com/zcPCr3
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

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!