fork download
copy 
  1. /**
  2.  * DA-IICT
  3.  * Author : PARTH PATEL
  4.  */
  5. import java.io.*;
  6. import java.math.*;
  7. import java.util.*;
  8.  
  9. import static java.util.Arrays.fill;
  10. import static java.lang.Math.*;
  11. import static java.util.Arrays.sort;
  12. import static java.util.Collections.sort;
  13.  
  14.  
  15.  class MKTHNUM {
  16.  
  17. 	public static long mod = 1000000007;
  18. 	public static long INF = (1L << 60);
  19. 	static FastScanner2 in = new FastScanner2();
  20. 	static OutputWriter out = new OutputWriter(System.out);
  21. 	static int n,m;
  22. 	static int[] arr;
  23. 	static ArrayList<Integer>[] tree;
  24. 	public static void buildtree(int node,int start,int end)
  25. 	{
  26. 		if(start==end)
  27. 		{
  28. 			tree[node].add(arr[start]);
  29. 			return;
  30. 		}
  31. 		int mid=(start+end)/2;
  32. 		buildtree(2*node, start, mid);
  33. 		buildtree(2*node+1, mid+1, end);
  34. 		tree[node]=merge(tree[2*node], tree[2*node+1]);
  35. 	}
  36. 	public static int querytree(int node,int start,int end,int l,int r,int k)
  37. 	{
  38. 		if(r<start || end<l)
  39. 		{
  40. 			return 0;
  41. 		}
  42. 		if(l<=start && end<=r)
  43. 		{
  44. 			if(l==r)
  45. 			{
  46. 				if(arr[start]>k)
  47. 					return 0;
  48. 				return 1;
  49. 			}
  50. 			int low=0;
  51. 			int high=tree[node].size()-1;
  52. 			// binary search returns number of elements smaller than or equal to k in given list
  53. 			while(low<=high)
  54. 			{
  55. 				int mid=(low+high)/2;
  56. 				if(tree[node].get(mid)>k)
  57. 				{
  58. 					high=mid-1;
  59. 				}
  60. 				else
  61. 				{
  62. 					low=mid+1;
  63. 				}
  64. 			}
  65. 			return low;
  66. 		}
  67. 		int mid=(start+end)/2;
  68. 		int p1=querytree(2*node, start, mid, l, r, k);
  69. 		int p2=querytree(2*node+1, mid+1, end, l, r, k);
  70. 		return (p1+p2);
  71. 	}
  72. 	public static ArrayList<Integer> merge(ArrayList<Integer> list1, ArrayList<Integer> list2)
  73. 	{
  74. 		ArrayList<Integer> merged=new ArrayList<>();
  75. 		int i=0;
  76. 		int j=0;
  77. 		while(i<list1.size() && j<list2.size())
  78. 		{
  79. 			if(list1.get(i)>list2.get(j))
  80. 			{
  81. 				merged.add(list2.get(j));
  82. 				j++;
  83. 			}
  84. 			else
  85. 			{
  86. 				merged.add(list1.get(i));
  87. 				i++;
  88. 			}
  89. 		}
  90. 		while(i<list1.size())
  91. 		{
  92. 			merged.add(list1.get(i));
  93. 			i++;
  94. 		}
  95. 		while(j<list2.size())
  96. 		{
  97. 			merged.add(list2.get(j));
  98. 			j++;
  99. 		}
  100. 		return merged;
  101. 	}
  102. 	public static void main(String[] args) {
  103.  
  104. 		n=in.nextInt();
  105. 		tree=new ArrayList[4*n+1000];
  106. 		for(int i=0;i<4*n+1000;i++)
  107. 		{
  108. 			tree[i]=new ArrayList<>();
  109. 		}
  110. 		m=in.nextInt();
  111. 		arr=new int[n];
  112. 		for(int i=0;i<n;i++)
  113. 		{
  114. 			arr[i]=in.nextInt();
  115. 		}
  116. 		buildtree(1, 0, n-1);
  117. 		while(m-->0)
  118. 		{
  119. 			int l=in.nextInt();
  120. 			int r=in.nextInt();
  121. 			int k=in.nextInt(); // obtain k-th number in this sorted segment
  122. 			long low=(int) -1e9;
  123. 			long high=(int)1e9;
  124. 			int answer = 0;
  125. 			if(l==r)
  126. 			{
  127. 				out.println(arr[l-1]);
  128. 				continue;
  129. 			}
  130. 			while(low<=high)
  131. 			{
  132. 				long mid=(low+high)/2;
  133. 				int query=querytree(1, 0, n-1, l-1, r-1, (int)mid);
  134.  
  135. 				if(query==k)
  136. 				{
  137. 					answer=(int) mid;
  138. 					break;
  139. 				}
  140. 				if(query>k)
  141. 				{
  142. 					high=mid-1;
  143. 				}
  144. 				if(query<k)
  145. 				{
  146. 					low=mid+1;
  147. 				}
  148. 			}
  149. 			out.println(answer);
  150. 		}
  151. 		out.close();
  152.  
  153. 	}
  154.  
  155. 	public static long pow(long x, long n, long mod) {
  156. 		long res = 1;
  157. 		for (long p = x; n > 0; n >>= 1, p = (p * p) % mod) {
  158. 			if ((n & 1) != 0) {
  159. 				res = (res * p % mod);
  160. 			}
  161. 		}
  162. 		return res;
  163. 	}
  164.  
  165. 	public static long gcd(long n1, long n2) {
  166. 		long r;
  167. 		while (n2 != 0) {
  168. 			r = n1 % n2;
  169. 			n1 = n2;
  170. 			n2 = r;
  171. 		}
  172. 		return n1;
  173. 	}
  174.  
  175. 	public static long lcm(long n1, long n2) {
  176. 		long answer = (n1 * n2) / (gcd(n1, n2));
  177. 		return answer;
  178. 	}
  179.  
  180. 	static class FastScanner2 {
  181. 		private byte[] buf = new byte[1024];
  182. 		private int curChar;
  183. 		private int snumChars;
  184.  
  185. 		public int read() {
  186. 			if (snumChars == -1)
  187. 				throw new InputMismatchException();
  188. 			if (curChar >= snumChars) {
  189. 				curChar = 0;
  190. 				try {
  191. 					snumChars = System.in.read(buf);
  192. 				} catch (IOException e) {
  193. 					throw new InputMismatchException();
  194. 				}
  195. 				if (snumChars <= 0)
  196. 					return -1;
  197. 			}
  198. 			return buf[curChar++];
  199. 		}
  200.  
  201. 		public String nextLine() {
  202. 			int c = read();
  203. 			while (isSpaceChar(c))
  204. 				c = read();
  205. 			StringBuilder res = new StringBuilder();
  206. 			do {
  207. 				res.appendCodePoint(c);
  208. 				c = read();
  209. 			} while (!isEndOfLine(c));
  210. 			return res.toString();
  211. 		}
  212.  
  213. 		public String nextString() {
  214. 			int c = read();
  215. 			while (isSpaceChar(c))
  216. 				c = read();
  217. 			StringBuilder res = new StringBuilder();
  218. 			do {
  219. 				res.appendCodePoint(c);
  220. 				c = read();
  221. 			} while (!isSpaceChar(c));
  222. 			return res.toString();
  223. 		}
  224.  
  225. 		public long nextLong() {
  226. 			int c = read();
  227. 			while (isSpaceChar(c))
  228. 				c = read();
  229. 			int sgn = 1;
  230. 			if (c == '-') {
  231. 				sgn = -1;
  232. 				c = read();
  233. 			}
  234. 			long res = 0;
  235. 			do {
  236. 				if (c < '0' || c > '9')
  237. 					throw new InputMismatchException();
  238. 				res *= 10;
  239. 				res += c - '0';
  240. 				c = read();
  241. 			} while (!isSpaceChar(c));
  242. 			return res * sgn;
  243. 		}
  244.  
  245. 		public int nextInt() {
  246. 			int c = read();
  247. 			while (isSpaceChar(c))
  248. 				c = read();
  249. 			int sgn = 1;
  250. 			if (c == '-') {
  251. 				sgn = -1;
  252. 				c = read();
  253. 			}
  254. 			int res = 0;
  255. 			do {
  256. 				if (c < '0' || c > '9')
  257. 					throw new InputMismatchException();
  258. 				res *= 10;
  259. 				res += c - '0';
  260. 				c = read();
  261. 			} while (!isSpaceChar(c));
  262. 			return res * sgn;
  263. 		}
  264.  
  265. 		public int[] nextIntArray(int n) {
  266. 			int[] arr = new int[n];
  267. 			for (int i = 0; i < n; i++) {
  268. 				arr[i] = nextInt();
  269. 			}
  270. 			return arr;
  271. 		}
  272.  
  273. 		public long[] nextLongArray(int n) {
  274. 			long[] arr = new long[n];
  275. 			for (int i = 0; i < n; i++) {
  276. 				arr[i] = nextLong();
  277. 			}
  278. 			return arr;
  279. 		}
  280.  
  281. 		private boolean isSpaceChar(int c) {
  282. 			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  283. 		}
  284.  
  285. 		private boolean isEndOfLine(int c) {
  286. 			return c == '\n' || c == '\r' || c == -1;
  287. 		}
  288. 	}
  289.  
  290. 	static class InputReader {
  291. 		public BufferedReader reader;
  292. 		public StringTokenizer tokenizer;
  293.  
  294. 		public InputReader(InputStream inputstream) {
  295. 			reader = new BufferedReader(new InputStreamReader(inputstream));
  296. 			tokenizer = null;
  297. 		}
  298.  
  299. 		public String nextLine() {
  300. 			String fullLine = null;
  301. 			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  302. 				try {
  303. 					fullLine = reader.readLine();
  304. 				} catch (IOException e) {
  305. 					throw new RuntimeException(e);
  306. 				}
  307. 				return fullLine;
  308. 			}
  309. 			return fullLine;
  310. 		}
  311.  
  312. 		public String next() {
  313. 			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  314. 				try {
  315. 					tokenizer = new StringTokenizer(reader.readLine());
  316. 				} catch (IOException e) {
  317. 					throw new RuntimeException(e);
  318. 				}
  319. 			}
  320. 			return tokenizer.nextToken();
  321. 		}
  322.  
  323. 		public long nextLong() {
  324. 			return Long.parseLong(next());
  325. 		}
  326.  
  327. 		public int[] nextIntArray(int n) {
  328. 			int a[] = new int[n];
  329. 			for (int i = 0; i < n; i++) {
  330. 				a[i] = nextInt();
  331. 			}
  332. 			return a;
  333. 		}
  334.  
  335. 		public long[] nextLongArray(int n) {
  336. 			long a[] = new long[n];
  337. 			for (int i = 0; i < n; i++) {
  338. 				a[i] = nextLong();
  339. 			}
  340. 			return a;
  341. 		}
  342.  
  343. 		public int nextInt() {
  344. 			return Integer.parseInt(next());
  345. 		}
  346. 	}
  347.  
  348. 	static class OutputWriter {
  349. 		private final PrintWriter writer;
  350.  
  351. 		public OutputWriter(OutputStream outputStream) {
  352. 			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  353. 		}
  354.  
  355. 		public OutputWriter(Writer writer) {
  356. 			this.writer = new PrintWriter(writer);
  357. 		}
  358.  
  359. 		public void print(Object... objects) {
  360. 			for (int i = 0; i < objects.length; i++) {
  361. 				if (i != 0)
  362. 					writer.print(' ');
  363. 				writer.print(objects[i]);
  364. 			}
  365. 		}
  366.  
  367. 		public void println(Object... objects) {
  368. 			print(objects);
  369. 			writer.println();
  370. 		}
  371.  
  372. 		public void close() {
  373. 			writer.close();
  374. 		}
  375.  
  376. 		public void flush() {
  377. 			writer.flush();
  378. 		}
  379. 	}
  380.  
  381. }
  382.  
Success #stdin #stdout 0.1s 28180KB
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/sqKKVQ
language:
Java (HotSpot 12)
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!