fork download
copy 
  1. #include<cstdio>
  2. #include<algorithm>
  3. using namespace std;
  4. struct Node
  5. {
  6.     int sum_left,sum_right,sum_max,sum_total;
  7.     bool indicator;
  8. };
  9. const int MAX = 50010;
  10. const int INF = -9999999;
  11. Node tree[MAX<<2];
  12. int arr[MAX],n;
  13. void input()
  14. {
  15.     scanf("%d", &n);
  16.     int i;
  17.     for(i=1;i<=n;i++)
  18.         scanf("%d", &arr[i]);
  19. }
  20. void Build_tree(int a, int b, int node)
  21. {
  22.     if(a>b)
  23.         return;
  24.     if(a==b)
  25.     {
  26.         tree[node].sum_left=tree[node].sum_right=tree[node].sum_max=tree[node].sum_total=arr[a];
  27.         tree[node].indicator=1;
  28.         return;
  29.     }
  30.     Build_tree(a,(a+b)>>1,node<<1);
  31.     Build_tree(((a+b)>>1)+1,b,(node<<1)+1);
  32.     tree[node].sum_total=tree[node<<1].sum_total+tree[(node<<1)+1].sum_total;
  33.     tree[node].sum_left=max(tree[node<<1].sum_left,tree[node<<1].sum_total+tree[(node<<1)+1].sum_left);
  34.     tree[node].sum_right=max(tree[(node<<1)+1].sum_right,tree[(node<<1)+1].sum_total+tree[node<<1].sum_right);
  35.     tree[node].sum_max=max(tree[node<<1].sum_max,tree[(node<<1)+1].sum_max);
  36.     tree[node].sum_max=max(tree[node].sum_max,tree[node].sum_left);
  37.     tree[node].sum_max=max(tree[node].sum_max,tree[node].sum_right);
  38.     tree[node].sum_max=max(tree[node].sum_max,tree[node].sum_total);
  39.     tree[node].sum_max=max(tree[node].sum_max,tree[node<<1].sum_right+tree[(node<<1)+1].sum_left);
  40.     if(tree[node].sum_max==tree[node].sum_total)
  41.         tree[node].indicator=1;
  42.     else
  43.         tree[node].indicator=0;
  44. }
  45. Node Query_tree(int a, int b, int i, int j, int node)
  46. {
  47.     if(a>b || a>j || b<i)
  48.     {
  49.         Node p;
  50.         p.sum_left=p.sum_right=p.sum_max=p.sum_total=INF;
  51.         p.indicator=1;
  52.         return p;
  53.     }
  54.     if(a>=i && b<=j)
  55.         return tree[node];
  56.     Node q1,q2;
  57.     q1=Query_tree(a,(a+b)>>1,i,j,node<<1);
  58.     q2=Query_tree(((a+b)>>1)+1,b,i,j,(node<<1)+1);
  59.     Node p;
  60.     p.sum_total=q1.sum_total+q2.sum_total;
  61.     p.sum_left=max(q1.sum_left,q1.sum_total+q2.sum_left);
  62.     p.sum_right=max(q2.sum_right,q2.sum_total+q1.sum_right);
  63.     p.sum_max=max(q1.sum_max,q2.sum_max);
  64.     p.sum_max=max(p.sum_max,p.sum_left);
  65.     p.sum_max=max(p.sum_max,p.sum_right);
  66.     p.sum_max=max(p.sum_max,p.sum_total);
  67.     p.sum_max=max(p.sum_max,q1.sum_right+q2.sum_left);
  68.     if(p.sum_max==p.sum_total)
  69.         p.indicator=1;
  70.     else
  71.         p.indicator=0;
  72.     return p;
  73. }
  74. void solve()
  75. {
  76.     Build_tree(1,n,1);
  77.     int i,m,x,y;
  78.     scanf("%d", &m);
  79.     Node p;
  80.     for(i=1;i<=m;i++)
  81.     {
  82.         scanf("%d %d", &x, &y);
  83.         p=Query_tree(1,n,x,y,1);
  84.         printf("%d\n", p.sum_max);
  85.     }
  86. }
  87. int main()
  88. {
  89.     input();
  90.     solve();
  91.     return 0;
  92. }
  93.  
  94.  
Success #stdin #stdout 0s 7440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bEwKPy
language:
C++14 (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!