fork download
copy 
  1. #include<bits/stdc++.h>
  2. int *arr,*st;
  3. long long max;
  4.  
  5. int construct(int s, int e,int i)
  6. {
  7.     if(s==e)
  8.     {
  9.         st[i]=arr[s];
  10.         if(st[i]>max)
  11.             max=st[i];
  12.         return st[i];
  13.     }
  14.     int mid=(s+e)/2;
  15.     st[i]=construct(s,mid,2*i+1)+construct(mid+1,e,2*i+2);
  16.     if(st[i]>max)
  17.         max=st[i];
  18.     return st[i];
  19. }
  20.  
  21. int getSum(int s,int e,int qs,int qe,int i)
  22. {
  23.     if(s>=qs&&e<=qe)
  24.         return st[i];
  25.     if(e<qs||s>qe)
  26.         return 0;
  27.  
  28.     int mid=(s+e)/2;
  29.     return getSum(s,mid,qs,qe,2*i+1)+getSum(mid+1,e,qs,qe,2*i+2);
  30.  
  31. }
  32. int main()
  33. {
  34.     int n;
  35.     scanf("%d",&n);
  36.     arr=new int[n];
  37.     for(int i=0;i<n;i++)
  38.     {
  39.         scanf("%d",&arr[i]);
  40.     }
  41.     int x=(int)(ceil(log2(n)));
  42.     x++;
  43.     int m=2*(int)pow(2,x)-1;
  44.     st=new int[n+1];
  45.     construct(0,n-1,0);
  46.  
  47.   /*  printf("\n");
  48.     for(int i=0;i<30;i++)
  49.         printf("%d ",st[i]);
  50.  
  51.         printf("reached");
  52.    fflush(stdin);*/
  53.   int l;
  54.   scanf("%d",&l);
  55.    //     printf("reached ");
  56.         while(l--)
  57.         {
  58.             int x,y;
  59.             scanf("%d%d",&x,&y);
  60.             x--;
  61.             y--;
  62.             max=0;
  63.             for(int i=x;i<=y;i++)
  64.             {
  65.                 if(arr[i]>max)
  66.                     max=arr[i];
  67.             }
  68.             if(x!=y){
  69.             int z=getSum(0,n-1,x,y,0);
  70.             if(z>max)
  71.                 max=z;
  72.             }
  73.              printf("%d\n",max);
  74.         }
  75.  
  76.  
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 3232KB
comments (?)
stdin
copy 
10
1 2 3 4 5 6 7 8 9 10
4
1 3
2 5
3 4
stdout
copy 
6
14
7
5
https://ideone.com/HPev59
language:
C++ (gcc 8.3)
created:
9 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!