fork download
copy 
  1. #include<stdio.h>
  2. #define INF -99999999
  3. typedef long long ll;
  4. ll arr[50009],tree[500000];
  5. void create(ll node,ll left,ll right)
  6. {
  7. 	if(left==right)
  8. 	{
  9. 		tree[node]=arr[left];
  10. 		return;
  11. 	}
  12. 	ll mid=left+right;
  13. 	mid/=2;
  14. 	create(2*node+1,left,mid);
  15. 	create(2*node+2,mid+1,right);
  16. 	tree[node]=tree[2*node+1]+tree[2*node+2];
  17. }
  18. ll query(ll node,ll left,ll right,ll i,ll j)	//left and right = interval,,,i and j are present interval and changeable
  19. {
  20. 	if(i>j || i>right || j<left)		//completely outside of required interval
  21. 		return INF;
  22. 	if(i==j && i>=left && j<=right)		//single element interval inside required interval must be maximum of that interval
  23. 		return tree[node];
  24. 	ll max;
  25. 	if(i>=left && j<=right && i<=j)		//Inside interval
  26. 	{
  27. 		max=tree[node];
  28. 	}
  29. 	else
  30. 		max=INF;
  31. 	ll mid=i+j;
  32. 		mid/=2;
  33. 	ll a=query(2*node+1,left,right,i,mid);		//finding max in left sub-tree
  34. 	ll b=query(2*node+2,left,right,mid+1,j);	//finding max in right sub-tree
  35.  
  36. 	if(a>max)
  37. 		max=a;
  38. 	if(b>max)
  39. 		max=b;
  40. 	return max;
  41. 	//printf("HII:i = %lld j = %lld\nHii:left = %lld right = %lld\n",i,j,left,right);
  42. }
  43. int main()
  44. {
  45. 	ll n,q,a,b;
  46. 	scanf("%lld",&n);
  47. 	for(int i=0;i<n;i++)
  48. 		scanf("%lld",&arr[i]);
  49. 	create(1,0,n-1);
  50. 	scanf("%lld",&q);
  51. 	while(q--)
  52. 	{
  53. 		scanf("%lld%lld",&a,&b);
  54. 		a--;
  55. 		b--;
  56. 		printf("%lld\n",query(1,a,b,0,n-1));
  57. 	}
  58. }
Success #stdin #stdout 0s 6984KB
comments (?)
stdin
copy 
3
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/C4jZxo
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!