fork download
copy 
  1. #include<stdio.h>
  2. #include<string.h>
  3. #define INF -99999999;
  4. typedef long long ll;
  5. ll arr[50009];
  6. struct segment
  7. {
  8. 	ll sum,max;
  9. };
  10. struct segment tree[500009];  
  11. ll maximum(ll a,ll b,ll c)
  12. {
  13. 	ll ans=a;
  14. 	if(b>ans)
  15. 		ans=b;
  16. 	if(c>ans)
  17. 		ans=c;
  18. 	return ans;
  19. }
  20. void create(ll node, ll left, ll right)
  21. {
  22. 	if(left==right)
  23. 	{
  24. 		tree[node].sum=tree[node].max=arr[left];
  25. 		return;
  26. 	}
  27. 	ll mid=left+right;
  28. 	mid/=2;
  29. 	create(2*node,left,mid);
  30. 	create(2*node+1,mid+1,right);
  31.  
  32. 	tree[node].sum=tree[2*node].sum+tree[2*node+1].sum;
  33. 	tree[node].max=maximum(tree[node].sum,tree[2*node].max,tree[2*node+1].max);
  34. }
  35. ll query(ll node, ll left, ll right, ll i, ll j)
  36. {
  37. 	if(i>j || i>right || j<left)
  38. 		return INF;
  39. 	if(i==j && i>=left && j<=right)	//Inside the interval, single element
  40. 		return tree[node].max;
  41. 	ll max;
  42. 	if(i>=left && j<=right)
  43. 		max=tree[node].max;
  44. 	else
  45. 		max=INF;
  46. 	ll mid=i+j;
  47. 	mid/=2;
  48. 	ll a=query(2*node,left,right,i,mid);
  49. 	ll b=query(2*node+1,left,right,mid+1,j);
  50.  
  51. 	return maximum(max,a,b);
  52.  
  53. }
  54. int main()
  55. {
  56. 	//memset(tree,0,sizeof(struct segment)*500009);
  57. 	ll n,q,a,b;
  58. 	scanf("%lld",&n);
  59. 	for(int i=0;i<n;i++)
  60. 		scanf("%lld",&arr[i]);
  61. 	create(1,0,n-1);
  62. 	scanf("%lld",&q);
  63. 	while(q--)
  64. 	{
  65. 		scanf("%lld%lld",&a,&b);
  66. 		a--;
  67. 		b--;
  68. 		printf("%lld\n",query(1,a,b,0,n-1));
  69. 	}
  70. }
Success #stdin #stdout 0s 10936KB
comments (?)
stdin
copy 
3
-1 2 3
1
1 2
stdout
copy 
2
https://ideone.com/MkHBSB
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!