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