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