fork(10) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. typedef long long lld;
  4. typedef unsigned long long llu;
  5. #define rep(i,x,y)  for(i=x;i<y;i++)
  6. #define rrep(i,x,y) for(i=x;i>=y;i--)
  7. #define trv(y,x)    for(typeof(x.begin())y=x.begin();y!=x.end();y++)
  8. #define MID(x,y)    (x+((y-x)/2))
  9. using namespace std;
  10.  
  11.  
  12. #define MAX (1<<16)
  13. #define MAX2 (MAX<<2)
  14.  
  15.  
  16.  
  17.  
  18. int A[MAX];
  19. struct node
  20. {
  21.     int bestleftsum,bestrightsum,sum,bestsum;
  22.     void Merge(node &A,node &B)
  23.     {
  24.         sum=A.sum+B.sum;
  25.         bestleftsum=max(A.bestleftsum,A.sum+B.bestleftsum);
  26.         bestrightsum=max(A.bestrightsum+B.sum,B.bestrightsum);
  27.         bestsum=max(max(A.bestsum,B.bestsum),A.bestrightsum+B.bestleftsum);
  28.     }
  29.     void CreateLeaf(int val)
  30.     {
  31.         sum=bestleftsum=bestrightsum=bestsum=val;
  32.     }
  33. };
  34.  
  35.  
  36.  
  37.     node T[MAX2];
  38.     void init(int index,int l,int r)
  39.     {
  40.         if(l==r)
  41.             {
  42.                 T[index].CreateLeaf(A[l]);
  43.                 return;
  44.             }
  45.         else
  46.         {
  47.             int mid=MID(l,r);
  48.             init(2*index,l,mid);
  49.             init(2*index+1,mid+1,r);
  50.             T[index].Merge(T[2*index],T[2*index+1]);
  51.         }
  52.  
  53.     }
  54.     void query(node& result,int l,int r,int u,int v,int index)
  55.     {
  56.         if(u==l && v==r)
  57.             {
  58.                 result=T[index];
  59.                 return;
  60.             }
  61.         else
  62.         {
  63.            int mid=MID(l,r);
  64.            if(mid>=v)
  65.                 query(result,l,mid,u,v,2*index);
  66.             else if(mid<u)
  67.                 query(result,mid+1,r,u,v,2*index+1);
  68.             else
  69.             {
  70.                 node left,right;
  71.                 query(left,l,mid,u,mid,2*index);
  72.                 query(right,mid+1,r,mid+1,v,2*index+1);
  73.                 result.Merge(left,right);
  74.  
  75.           	} 
  76.          }
  77.     } 
  78.  
  79. int main()
  80. {
  81.     ios_base::sync_with_stdio(false);
  82. 	cin.tie(NULL);
  83.     int n,t,x,y;
  84.     cin>>n;
  85.     for(int i=0;i<n;i++)
  86.         cin>>A[i];
  87.     init(1,0,n-1);
  88.     cin>>t;
  89.     node Ans;
  90.     while(t--)
  91.     {
  92.         cin>>x>>y;
  93.         query(Ans,0,n-1,x-1,y-1,1);
  94.         cout<<Ans.bestsum<<"\n";
  95.     }
  96.  
  97.  
  98.  
  99.     return 0;
  100. }
Success #stdin #stdout 0s 7816KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/Qq25J5
language:
C++ (gcc 8.3)
created:
7 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!