fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxx 1 << 16
  4. struct node
  5. {
  6.     long pre;
  7.     long suff;
  8.     long sum;
  9.     long maxsum;
  10. };
  11. struct node tree[maxx<<1];
  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(max(temp.sum,temp.pre),temp.suff);
  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.         return;
  30.     }
  31.     else
  32.     {
  33.         int mid=(low+high)>>1;
  34.         build(a,2*pos,low,mid);
  35.         build(a,2*pos+1,mid+1,high);
  36.         tree[pos]=merge(tree[2*pos],tree[2*pos+1]);
  37.     }
  38. }
  39. node query(int pos,int low,int high,int qlow,int qhigh)
  40. {
  41.     if(qlow>=low && qhigh<=high)tree[pos];
  42.     int mid=(low+high)>>1;
  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.         cout<<query(0,0,n-1,--x,--y).maxsum<<endl;
  62.     }
  63.     return  0;
  64. }
  65.  
Runtime error #stdin #stdout 0s 13248KB
comments (?)
stdin
copy 
3 
-1 2 3
1
1 2
stdout
copy 
Standard output is empty
https://ideone.com/kDFiNY
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!