fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<math.h>
  3.  
  4. typedef int ull;
  5.  
  6. #define MAX 100000
  7. ull max;
  8. ull arr[MAX];
  9. ull constructF(ull ss,ull se,ull *st,ull si)
  10. {
  11.     if(ss==se)
  12.     {
  13.         st[si]=arr[ss];
  14.         return st[si];
  15.     }
  16.  
  17.     ull mid=(se+ss)/2;
  18.  
  19.     st[si]=constructF(ss,mid,st,2*si+1)+constructF(mid+1,se,st,2*si+2);
  20.  
  21.     return st[si];
  22. }
  23.  
  24. ull *construct(ull n)
  25. {
  26.     ull x=(ceil(log2(n)));
  27.     ull max_size=2*pow(2,x)-1;
  28.     ull *st=new ull[max_size];
  29.  
  30.     constructF(0,n-1,st,0);
  31.     return st;
  32. }
  33.  
  34. ull getSumF(ull *st,ull ss,ull se,ull qs,ull qe,ull index)
  35. {
  36.     if(ss>=qs&&se<=qe)
  37.     {
  38.         if(max<st[index])
  39.             max=st[index];
  40.         if(ss!=se)
  41.         {
  42.             ull mid=(ss+se)/2;
  43.             getSumF(st,ss,mid,qs,qe,2*index+1);
  44.             getSumF(st,mid+1,se,qs,qe,2*index+2);
  45.         }
  46.         return st[index];
  47.     }
  48.  
  49.     if(se<qs||ss>qe)
  50.     {
  51.         return 0;
  52.     }
  53.     ull mid = (se+ss)/2;
  54.     ull val=getSumF(st,ss,mid,qs,qe,2*index+1)+getSumF(st,mid+1,se,qs,qe,2*mid+2);
  55.     if(max<val)
  56.         max=val;
  57.  
  58.     return val;
  59. }
  60. /*ull getSum(ull arr[],ull *st,ull n,ull qs,ull qe)
  61. {
  62.     if(qs<0||qe>n-1||qs>qe)
  63.         return 0;
  64.  
  65.  
  66. }*/
  67. int main()
  68. {
  69.     ull n;
  70.     scanf("%d",&n);
  71.  
  72.     for(ull i=0;i<n;i++)
  73.     {
  74.         scanf("%d",&arr[i]);
  75.     }
  76.     ull m;
  77.     scanf("%d",&m);
  78.     ull *st=construct(n);
  79.     while(m--)
  80.     {
  81.         ull x,y;
  82.         max=-10000;
  83.         scanf("%d%d",&x,&y);
  84.         //getSum(arr,st,n,x-1,y-1);
  85.         getSumF(st,0,n-1,x-1,y-1,0);
  86.         printf("%d\n",max);
  87.     }
  88.     return 0;
  89. }
  90.  
Runtime error #stdin #stdout #stderr 0s 4552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/OQCV8l
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!