fork download
copy 
  1. #include <stdio.h>
  2. #include<limits.h>
  3. /*
  4. void update_val(int seg [] , int low ,int high , int index , int diff, int pos)
  5. {
  6. 	int mid;
  7. 	if(index<low||index>high)
  8. 	return;
  9. 	seg[pos] = seg[pos]+diff;
  10. 	if(high!=low)
  11. 	{
  12. 		mid = (low+high)/2;
  13. 		update_val(seg,low,mid,index,diff,2*pos+1);
  14. 		update_val(seg,mid+1,high,index,diff,2*pos+2);
  15. 	}
  16. }
  17. */
  18. int min(int a, int b)
  19. {
  20. 	return a>b ?b:a;
  21. }
  22. int max(int a, int b)
  23. {
  24. 	return a>b ?a:b;
  25. }
  26. void constructTree(int arr [] , int seg[] , int low, int high , int pos)
  27. {
  28. 	int mid;
  29. 	if(low==high)
  30. 	{
  31. 		seg[pos]=arr[low];
  32. 		return;
  33. 	}
  34. 	mid  = (low+high)/2;
  35. 	constructTree(arr,seg,low,mid,2*pos+1);
  36. 	constructTree(arr,seg,mid+1,high,2*pos+2);
  37. 	seg[pos] = min(seg[2*pos+1],seg[2*pos+2]);
  38. }
  39. void newconstructTree(int arr [] , int newseg[] , int low, int high , int pos)
  40. {
  41. 	int mid;
  42. 	if(low==high)
  43. 	{
  44. 		newseg[pos]=arr[low];
  45. 		return;
  46. 	}
  47. 	mid  = (low+high)/2;
  48. 	newconstructTree(arr,newseg,low,mid,2*pos+1);
  49. 	newconstructTree(arr,newseg,mid+1,high,2*pos+2);
  50. 	newseg[pos] = max(newseg[2*pos+1],newseg[2*pos+2]);
  51. }
  52. int newrangeQuery(int newseg[],int qlow , int qhigh , int low , int high , int pos)
  53. {
  54. 	if(qlow<=low && qhigh>=high)
  55. 	{
  56. 		return newseg[pos];
  57. 	}
  58. 	if(qlow>high || qhigh <low)
  59. 	{
  60. 		return INT_MIN;
  61. 	}
  62. 	int mid = (low+high)/2;
  63. 	return max(newrangeQuery(newseg,qlow,qhigh,low,mid,2*pos+1),newrangeQuery(newseg,qlow,qhigh,mid+1,high,2*pos+2));
  64.  
  65. }
  66. int rangeQuery(int seg[],int qlow , int qhigh , int low , int high , int pos)
  67. {
  68. 	if(qlow<=low && qhigh>=high)
  69. 	{
  70. 		return seg[pos];
  71. 	}
  72. 	if(qlow>high || qhigh <low)
  73. 	{
  74. 		return INT_MAX;
  75. 	}
  76. 	int mid = (low+high)/2;
  77. 	return min(rangeQuery(seg,qlow,qhigh,low,mid,2*pos+1),rangeQuery(seg,qlow,qhigh,mid+1,high,2*pos+2));
  78.  
  79. }
  80. int main(void) {
  81. 	// your code goes here
  82. 	int arr[100010];
  83. 	int n,minimum,k,max1,max2,max3;
  84. 	float newmax,newmax2;
  85. 	int i,diff,l,r,q;
  86. 	int seg[300040]={0};
  87. 	int newseg[300040]={0};
  88. 	scanf("%d",&n);
  89. 	for(i=0;i<n;i++)
  90. 	{
  91. 		scanf("%d",&arr[i]);
  92. 	}
  93. 	constructTree(arr,seg,0,n-1,0);
  94.     /*
  95. 	for(i=0;i<63;i++)
  96. 	{
  97. 		printf("%d ",seg[i]);
  98. 	}
  99. 	printf("\n");
  100. 	*/
  101. 	newconstructTree(arr,newseg,0,n-1,0);
  102. 	scanf("%d",&q);
  103. 	for(k=0;k<q;k++)
  104. 	{
  105. 	scanf("%d%d",&l,&r);
  106. 	max1=max2=max3=-1;
  107. 	minimum = rangeQuery(seg,l,r,0,n-1,0);
  108. 	//printf("%d\n",minimum);
  109. 	if(l-1>=0)
  110. 	{
  111. 	max1 =newrangeQuery(newseg,0,l-1,0,n-1,0);
  112. 	}
  113. 	if(r+1<=n-1)
  114. 	{
  115. 	max2 =newrangeQuery(newseg,r+1,n-1,0,n-1,0); 
  116. 	}
  117. 		printf("%d\n",max1);
  118. 		printf("%d\n",max2);
  119. 		newmax = (float)(max(max1,max2)+minimum);
  120. 		printf("%f\n",newmax);
  121. 	max3 = newrangeQuery(newseg,l,r,0,n-1,0);
  122. 		printf("%d\n",max3);
  123. 		newmax2 = minimum+(max3-minimum)/2.0;
  124. 		if(newmax2>newmax)
  125. 		{
  126. 			printf("%.1f\n",newmax2);
  127. 		}
  128. 		else
  129. 		{
  130. 			printf("%.1f\n",newmax);
  131. 		}
  132. 	}
  133.  
  134. 	return 0;
  135. }
  136.  
Success #stdin #stdout 0s 4672KB
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 
4
3
9.000000
12
9.0
https://ideone.com/EvLByN
segment tree
language:
C (gcc 8.3)
created:
8 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!