fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAX 400000
  5. #define lld long long int
  6.  
  7. struct node
  8. {
  9.     lld data;
  10.     lld left;
  11.     lld right;
  12.     lld sum;
  13.  
  14.     node()
  15.     {
  16.         data =-1000000000;
  17.         left =-1000000000;
  18.         right=-1000000000;
  19.         sum  =-1000000000;
  20.     }
  21. }tree[MAX];
  22.  
  23. lld a[100005];
  24.  
  25. void init(int i,int start,int end)
  26. {
  27.     if(start==end)
  28.     {
  29.         tree[i].data = a[start];
  30.         tree[i].left = a[start];
  31.         tree[i].right = a[start];
  32.         tree[i].sum = a[start];
  33.         return;
  34.     }
  35.  
  36.     int mid = (start+end)/2;
  37.  
  38.     init(2*i,start,mid);
  39.     init(2*i+1,mid+1,end);
  40.  
  41.     tree[i].sum = tree[2*i].sum + tree[2*i+1].sum;
  42.     tree[i].left = tree[2*i].sum;
  43.     tree[i].right = tree[2*i+1].sum;
  44.  
  45.     tree[i].data = max(tree[i].sum,max(tree[i].left,tree[i].right));
  46.     tree[i].data = max(tree[i].data,max(tree[2*i].data,tree[2*i+1].data));
  47.     tree[i].data = max(tree[i].data,tree[2*i].right+tree[2*i+1].left);
  48.  
  49. }
  50. node query(int i,int start,int end,int qs,int qe)
  51. {
  52.     if(qs>end||qe<start)
  53.     {
  54.         node temp;
  55.         temp.data = 0;
  56.         return temp;
  57.     }
  58.     if(qs<=start&&qe>=end)
  59.     {
  60.         return tree[i];
  61.     }
  62.  
  63.     int mid = (start+end)/2;
  64.  
  65.     node id1 = query(2*i,start,mid,qs,qe);
  66.     node id2 = query(2*i+1,mid+1,end,qs,qe);
  67.  
  68.     if(id1.data==0)return id2;
  69.     if(id2.data==0)return id1;
  70.  
  71.     node r;
  72.  
  73.     r.data = max(id1.data,max(id2.data,max(id1.sum,max(id2.sum,id1.right+id2.left))));
  74.  
  75.     return r;
  76. }
  77. int main()
  78. {
  79.  
  80.     lld n,q;
  81.     int qs,qe;
  82.     scanf("%lld",&n);
  83.  
  84.     for(int i=0;i<n;i++)
  85.     scanf("%lld",&a[i]);
  86.  
  87.     init(1,0,n-1);
  88.     //for(int i=0;i<10;i++)
  89.     //cout<<tree[i].data<<" ";
  90.     scanf("%lld",&q);
  91.     while(q--)
  92.     {
  93.         scanf("%d%d",&qs,&qe);
  94.         qs--;qe--;
  95.  
  96.         printf("%lld\n",query(1,0,n-1,qs,qe).data);
  97.     }
  98.     return 0;
  99. }
  100.  
Success #stdin #stdout 0.01s 16584KB
comments (?)
stdin
copy 
21 
-2 -1 -1 -3 -2 -1 -3 -5 -1 -5 -1 -3 -3 -2 -7 -1 -3 -5 -1 -2 -5 
1 
1 20
stdout
copy 
-1
https://ideone.com/nlJ0ZK
language:
C++ (gcc 8.3)
created:
9 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!