fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define left(a) ((a*2)+1)
  5. #define right(a) ((a*2)+2)
  6.  
  7. #define leftsegment(start,end) start,(start+end)/2
  8. #define rightsegment(start,end) ((start+end)/2)+1,end
  9.  
  10. /*
  11. 	Use static arrays instead of pointers
  12. */
  13. int min[100000];
  14. int max[100000];
  15. int A[100000];
  16.  
  17. void initialize(int node,int start,int end)
  18. {
  19. 	if(start==end)
  20. 	{
  21. 		min[node]=A[start];
  22. 		max[node]=A[start];
  23. 		return;
  24. 	}
  25.  
  26. 	initialize(left(node),leftsegment(start,end));
  27. 	initialize(right(node),rightsegment(start,end));
  28.  
  29. 	if(min[left(node)]<=min[right(node)])
  30. 	{
  31. 		min[node]=min[left(node)];
  32. 	}
  33. 	else
  34. 	{
  35. 		min[node]=min[right(node)];
  36. 	}
  37.  
  38. 	if(max[left(node)]>=max[right(node)])
  39. 	{
  40. 		max[node]=max[left(node)];
  41. 	}
  42. 	else
  43. 	{
  44. 		max[node]=max[right(node)];
  45. 	}
  46. }
  47.  
  48. int minquery(int node,int start,int end,int qstart,int qend)
  49. {
  50. 	int minleft,minright;
  51.  
  52. 	if(qstart>end || qend<start)
  53. 	{
  54. 		return -1;
  55. 	}
  56.  
  57. 	if(start>=qstart && end<=qend)
  58. 	{
  59. 		return min[node];
  60. 	}
  61.  
  62. 	minleft=minquery(left(node),leftsegment(start,end),qstart,qend);
  63. 	minright=minquery(right(node),rightsegment(start,end),qstart,qend);
  64.  
  65. 	if(minleft==-1)
  66. 	{
  67. 		return minright;
  68. 	}
  69. 	if(minright==-1)
  70. 	{
  71. 		return minleft;
  72. 	}
  73. 	if(minleft<=minright)
  74. 	{
  75. 		return minleft;
  76. 	}
  77. 	return minright;
  78. }
  79.  
  80. int maxquery(int node,int start,int end,int qstart,int qend)
  81. {
  82. 	int maxleft,maxright;
  83.  
  84. 	if(qstart>end || qend<start)
  85. 	{
  86. 		return -1;
  87. 	}
  88.  
  89. 	if(start>=qstart && end<=qend)
  90. 	{
  91. 		return max[node];
  92. 	}
  93.  
  94. 	maxleft=maxquery(left(node),leftsegment(start,end),qstart,qend);
  95. 	maxright=maxquery(right(node),rightsegment(start,end),qstart,qend);
  96.  
  97. 	if(maxleft==-1)
  98. 	{
  99. 		return maxright;
  100. 	}
  101. 	if(maxright==-1)
  102. 	{
  103. 		return maxleft;
  104. 	}
  105. 	if(maxleft>=maxright)
  106. 	{
  107. 		return maxleft;
  108. 	}
  109. 	return maxright;
  110. }
  111.  
  112. int main(int argc, char **argv)
  113. {
  114. 	int N,Q,i,min1,max1,max2,max3,l,r;
  115. 	double t1,t2,t3,ans;
  116.  
  117. 	scanf("%d",&N);
  118. 	for(i=0;i<N;i++)
  119. 	{
  120. 		scanf("%d",&A[i]);
  121. 	}
  122.  
  123. 	initialize(0,0,N-1);
  124.  
  125. 	for(scanf("%d",&Q);Q>0;Q--)
  126. 	{
  127. 		scanf("%d%d",&l,&r);
  128.  
  129. 		min1=minquery(0,0,N-1,l,r);
  130. 		max1=maxquery(0,0,N-1,l,r);
  131. 		max1-=min1;
  132. 		max2=maxquery(0,0,N-1,0,l-1);
  133. 		max3=maxquery(0,0,N-1,r+1,N-1);
  134.  
  135. 		ans=min1;
  136. 		t1=max1/2.0;
  137. 		t2=max2;
  138. 		t3=max3;
  139.  
  140. 		if(t2<t3)t2=t3;
  141. 		if(t1<t2)t1=t2;
  142.  
  143. 		ans+=t1;
  144.  
  145. 		printf("%.1lf\n",ans);
  146. 	}
  147.  
  148. 	return 0;
  149. }
Success #stdin #stdout 0s 3468KB
comments (?)
stdin
copy 
18
3 4 2 1 5 7 9 7 10 5 12 3 1 1 2 1 3 2
1
4 10
stdout
copy 
9.0
https://ideone.com/W4Cj7S
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

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!