fork(1) download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxx 50009
  4. struct node
  5. {
  6.     long pre;
  7.     long suff;
  8.     long sum;
  9.     long maxsum;
  10. };
  11. struct node tree[4*maxx];
  12. node merge(node &a,node &b)
  13. {
  14.     node temp;
  15.     temp.sum=a.sum+b.sum;
  16.     temp.pre=max(a.pre,a.sum+b.pre);
  17.     temp.suff=max(b.suff,b.sum+a.suff);
  18.     temp.maxsum=max(a.maxsum,max(a.suff+b.pre,b.maxsum));
  19.     return temp;
  20. }
  21. void build(int a[],int pos,int low,int high)
  22. {
  23.     if(low==high)
  24.     {
  25.         tree[pos].maxsum=a[low];
  26.         tree[pos].sum=a[low];
  27.         tree[pos].pre=a[low];
  28.         tree[pos].suff=a[low];
  29.     }
  30.     else
  31.     {
  32.         int mid=(low+high)/2;
  33.         build(a,2*pos,low,mid);
  34.         build(a,2*pos+1,mid+1,high);
  35.         tree[pos]=merge(tree[2*pos],tree[2*pos+1]);
  36.     }
  37. }
  38. node query(int pos,int low,int high,int qlow,int qhigh)
  39. {
  40.     if(qlow>=low && qhigh<=high)
  41.     { return tree[pos];}
  42.     int mid=(low+high)/2;
  43.     node l=query(2*pos,low,mid,qlow,qhigh);
  44.     node r=query(2*pos+1,mid+1,high,qlow,qhigh);
  45.     tree[pos]=merge(l,r);
  46.     return tree[pos];
  47. }
  48. int main()
  49. {
  50.     int n;
  51.     cin>>n;
  52.     int a[maxx];
  53.     for(int i=0;i<n;i++)cin>>a[i];
  54.     build(a,0,0,n-1);
  55.     int Q;
  56.     cin>>Q;
  57.     while(Q--)
  58.     {
  59.         int x,y;
  60.         cin>>x>>y;
  61.         x-=1;
  62.         y-=1;
  63.         cout<<query(0,0,n-1,x,y).maxsum<<endl;
  64.     }
  65.     return  0;
  66. }
  67.  
Success #stdin #stdout 0s 6344KB
comments (?)
stdin 
3 
-1 2 3
1
1 2
stdout 
5
https://ideone.com/Wfd3Od
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!