fork(3) download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <iostream>
  4. using namespace std;
  5.  
  6. int n;
  7. int **a;
  8. int **st;
  9. int *size;
  10.  
  11. void fastscan(int &number){
  12.     //variable to indicate sign of input number
  13.     bool negative = false;
  14.     register int c;
  15.  
  16.     number = 0;
  17.  
  18.     // extract current character from buffer
  19.     c = getchar();
  20.     if (c=='-')
  21.     {
  22.         // number is negative
  23.         negative = true;
  24.  
  25.         // extract the next character from the buffer
  26.         c = getchar();
  27.     }
  28.  
  29.     // Keep on extracting characters if they are integers
  30.     // i.e ASCII Value lies from '0'(48) to '9' (57)
  31.     for (; (c>47 && c<58); c=getchar())
  32.         number = number *10 + c - 48;
  33.  
  34.     // if scanned input has a negative sign, negate the
  35.     // value of the input number
  36.     if (negative)
  37.         number *= -1;
  38. }
  39.  
  40.  
  41. int binarySearch(int s,int e,int arr[],int val){
  42. 	if(s < e){
  43. 		int mid = s + (e-s)/2;
  44. 		if(val >= arr[mid]){
  45. 			return binarySearch(mid+1,e,arr,val);
  46. 		}else{
  47. 			return binarySearch(s,mid,arr,val);
  48. 		}
  49. 	}
  50. 	return s;
  51. }
  52.  
  53. int query(int s,int e,int qs,int qe,int i,int k){
  54. 	if(s == e){
  55. 		return st[i][0];
  56. 	}
  57. 	int l1 = size[2*i+1];
  58. 	int upperBound = binarySearch(0,l1,st[2*i+1],qe);
  59. 	int lowerBound = binarySearch(0,l1,st[2*i+1],qs-1);
  60. 	int mid = s + (e-s)/2;
  61. 	if(upperBound - lowerBound >= k){
  62. 		return query(s,mid,qs,qe,2*i+1,k);
  63. 	}else{
  64. 		return query(mid+1,e,qs,qe,2*i+2,(k - (upperBound-lowerBound)));
  65. 	}
  66. }
  67.  
  68. void mergeST(int i){
  69. 	int left = 2*i+1;
  70. 	int right = 2*i+2;
  71. 	int l1 = size[left];
  72. 	int l2 = size[right];
  73. 	st[i] = (int *)(malloc(sizeof(int)*(l1+l2)));
  74. 	size[i] = l1 + l2;
  75. 	int a = 0;
  76. 	int b = 0;
  77. 	int c = 0;
  78. 	while(a<l1 && b<l2){
  79. 		if(st[left][a] <= st[right][b]){
  80. 			st[i][c++] = st[left][a++];
  81. 		}else{
  82. 			st[i][c++] = st[right][b++];
  83. 		}
  84. 	}
  85. 	while(a<l1){
  86. 		st[i][c++] = st[left][a++];
  87. 	}
  88. 	while(b<l2){
  89. 		st[i][c++] = st[right][b++];
  90. 	}
  91. }
  92.  
  93. void constructST(int s, int e,int i){
  94. 	if(e < s){
  95. 		return ;
  96. 	}
  97. 	if(e == s){
  98. 		st[i] = (int *)(malloc(sizeof(int)*1));
  99. 		st[i][0] = a[e][1];
  100. 		size[i] = 1;
  101. 		return ;
  102. 	}
  103. 	int mid = s + (e-s)/2;
  104. 	constructST(s,mid,2*i+1);
  105. 	constructST(mid+1,e,2*i+2);
  106. 	mergeST(i);
  107. }
  108.  
  109. void merge(int s,int mid,int e){
  110. 	int l1 = mid - s + 1;
  111. 	int l2 = e - mid;
  112. 	int ** l = (int **)(malloc(sizeof(int *)*l1));
  113. 	for(int i=0;i<l1;i++){
  114. 		l[i] = (int *)(malloc(sizeof(int)*2));
  115. 	}
  116. 	int ** r = (int **)(malloc(sizeof(int *)*l2));
  117. 	for(int i=0;i<l2;i++){
  118. 		r[i] = (int *)(malloc(sizeof(int)*2));
  119. 	}
  120. 	for(int i=0;i<l1;i++){
  121. 		l[i][0] = a[s+i][0];
  122. 		l[i][1] = a[s+i][1];
  123. 	}
  124. 	for(int i=0;i<l2;i++){
  125. 		r[i][0] = a[mid+i+1][0];
  126. 		r[i][1] = a[mid+i+1][1];
  127. 	}
  128. 	int i = 0;
  129. 	int j = 0;
  130. 	int k = s;
  131. 	while(i<l1 && j<l2){
  132. 		if(l[i][0] <= r[j][0]){
  133. 			a[k][0] = l[i][0];
  134. 			a[k++][1] = l[i++][1];
  135. 		}else{
  136. 			a[k][0] = r[j][0];
  137. 			a[k++][1] = r[j++][1];
  138. 		}
  139. 	}
  140. 	while(i<l1){
  141. 		a[k][0] = l[i][0];
  142. 		a[k++][1] = l[i++][1];
  143. 	}
  144. 	while(j<l2){
  145. 		a[k][0] = r[j][0];
  146. 		a[k++][1] = r[j++][1];
  147. 	}
  148. }
  149.  
  150. void mergeSort(int s,int e){
  151. 	if(s < e){
  152. 		int mid = s + (e-s)/2;
  153. 		mergeSort(s,mid);
  154. 		mergeSort(mid+1,e);
  155. 		merge(s,mid,e);
  156. 	}
  157. }
  158.  
  159. int main(){
  160. 	fastscan(n);
  161. //	scanf("%d",&n);
  162. 	int m;
  163. 	fastscan(m);
  164. //	scanf("%d",&m);
  165. 	int *tmp = (int *)(malloc(sizeof(int)*n));
  166. 	a = (int **)(malloc(sizeof(int *)*n));
  167. 	for(int i=0;i<n;i++){
  168. 		a[i] = (int *)(malloc(sizeof(int)*2));
  169. 	}
  170. 	for(int i=0;i<n;i++){
  171. 	//	scanf("%d",&a[i][0]);
  172. 		fastscan(a[i][0]);
  173. 		tmp[i] = a[i][0];
  174. 		a[i][1] = i;
  175. 	}
  176. 	mergeSort(0,n-1);
  177. 	st = (int **)(malloc(sizeof(int *)*263005));
  178. 	size = (int *)(malloc(sizeof(int)*263005));
  179. 	constructST(0,n-1,0);
  180. /*	for(int i=0;i<4*n;i++){
  181. 		for(int j=0;j<size[i];j++){
  182. 			printf("%d ",st[i][j]);
  183. 		}
  184. 		printf("\n");
  185. 	}
  186. */	while(m-- > 0){
  187. 		int l; 
  188. 		int r;
  189. 		int k;
  190. 	//	scanf("%d",&l);
  191. 	//	scanf("%d",&r);
  192. 	//	scanf("%d",&k);
  193. 		fastscan(l);
  194. 		fastscan(r);
  195. 		fastscan(k);
  196. 		l--;
  197. 		r--;
  198. 		printf("%d\n",tmp[query(0,n-1,l,r,0,k)]);
  199. 	}
  200. 	return 0;
  201. }
Success #stdin #stdout 0s 18328KB
comments (?)
stdin
copy 
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
stdout
copy 
5
6
3
https://ideone.com/qC2tVy
language:
C++ (gcc 8.3)
created:
6 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!