fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N=50000+5;
  4. int arr[N];
  5.  
  6. struct Node{
  7.   int bls,brs,bs,s;
  8.  
  9.   void merge(Node &A,Node &B){
  10.     s = A.s+B.s;
  11.     bls = max(A.bls,A.s+B.bls);
  12.     brs = max(B.brs,A.brs+B.s);
  13.     bs = max(max(A.bs,B.bs),A.brs+B.bls);
  14.   }
  15.  
  16.   void create(int val){
  17.     s=bs=bls=brs=val;
  18.   }
  19. };
  20. Node *st;
  21.  
  22. void buildTree(int index,int s,int e){
  23.   if(s==e){
  24.     st[index].create(arr[s]);
  25.     return;
  26.   }
  27.   int mid = (s+e)/2;
  28.   buildTree(2*index,s,mid);
  29.   buildTree(2*index+1,mid+1,e);
  30.   Node left = st[2*index];
  31.   Node right = st[2*index+1];
  32.   st[index].merge(left,right);
  33. }
  34.  
  35. Node query(int index,int s,int e,int qs,int qe){
  36.   if(qs<=s and qe>=e){
  37.     return st[index];
  38.   }
  39.   if(qs>e or qe<s)
  40.   {
  41.     Node nil;
  42.     nil.create(INT_MIN);
  43.     return nil;
  44.   }
  45.   int mid = (s+e)/2;
  46.   Node left = query(2*index,s,mid,qs,qe);
  47.   Node right = query(2*index+1,mid+1,e,qs,qe);
  48.  
  49.   Node a;
  50.   a.merge(left,right);
  51.   return a;
  52. }
  53.  
  54. int main() {
  55. 	st = new Node[4*N+5];
  56.  
  57.   int n;
  58.   cin>>n;
  59.   for(int i=0;i<n;i++){
  60.     cin>>arr[i];
  61.   }
  62.  
  63.   buildTree(1,0,n-1);
  64.  
  65.   int m;
  66.   cin>>m;
  67.  
  68.   while(m--){
  69.     int x,y;
  70.     cin>>x>>y;
  71.  
  72.     Node ans = query(1,0,n-1,x-1,y-1);
  73.     cout<<ans.bs<<endl;
  74.   }
  75. }
Runtime error #stdin #stdout 2.54s 4556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MVPSue
problem GSS1, based on SPOJ submission 24384670 (CPP14), 2019-09-12 17:46:02
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!