fork download
copy 
  1. import java.io.DataInputStream;
  2. import java.io.FileInputStream;
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5. //import java.util.Set;
  6. //import java.util.Collections;
  7. import java.util.StringTokenizer;
  8. //import java.util.TreeMap;
  9. import java.util.TreeSet;
  10.  
  11.  
  12.  
  13.  
  14.  
  15.  
  16. class ORDERSET {
  17.  
  18. 	public static void main(String[] args) throws IOException {
  19. 		// TODO Auto-generated method stub
  20. Reader r=new Reader();
  21.  
  22. StringBuilder sb=new StringBuilder();
  23. PrintWriter pr=new PrintWriter(System.out);
  24. int n=r.nextInt();
  25. //int countI=0,countD=0,countK=0,countC=0;
  26.  
  27. //TreeMap<Integer, Integer> tmap=new TreeMap<Integer, Integer>();
  28. TreeSet<Integer> tmap=new TreeSet<Integer>();
  29. int count=0;
  30. for(int i=1;i<=n;i++){
  31. 	String s=r.readLine();
  32. 	StringTokenizer st=new StringTokenizer(s);
  33. 	while(st.hasMoreTokens()){
  34. 		String q=st.nextToken();
  35. 		if(q.equals("I")){
  36.  
  37. 			int value=Integer.parseInt(st.nextToken());
  38.  
  39.  
  40. 				//countI++;
  41. 			tmap.add(value);
  42.  
  43. 			count=tmap.size();
  44.  
  45.  
  46.  
  47. 		}
  48.  
  49. 		else if(q.equals("D")){
  50.  
  51. 			int value=Integer.parseInt(st.nextToken());
  52.  
  53. 				//countD++;
  54. 			tmap.remove((Integer)value);
  55.  
  56. 			count=tmap.size();
  57.  
  58.  
  59. 		}
  60.  
  61. 		else if(q.equals("K")){
  62. 			//countK++;
  63.  
  64. 			int k=Integer.parseInt(st.nextToken());
  65.  
  66. 			if(k>count)sb.append("invalid\n");
  67. 			else{
  68.  
  69. 			//	Set<Integer> tss=tmap.keySet();
  70. 				Object a[]=tmap.toArray();
  71. 				Object value= binarySearch(a, k, count);
  72. 				sb.append(value+"\n");
  73.  
  74. 			}
  75.  
  76. 		}
  77. 		else{
  78. 			//countC++;
  79.  
  80. 			int k=Integer.parseInt(st.nextToken());
  81. 			k--;
  82.  
  83. 			//Set<Integer> tss=tmap.keySet();
  84. 			Object[] c=tmap.toArray();
  85. 			Object value=binarySearchCount(c, k, count);
  86. 			sb.append(value+"\n");
  87.  
  88. 		}
  89. 	}
  90.  
  91. 	//System.out.println(countI+" "+countD+" "+countK+" "+countC);
  92. }
  93. pr.write(sb.toString());
  94. pr.flush();
  95. 	}
  96. 	public static Object binarySearch(Object a[],int k,int count){
  97. 		k--;
  98. 		int low=0,high=count-1,mid=(low+((high-low+1)>>1)),prev_mid=mid;
  99. 		while(low<high){
  100. 			mid=(low+((high-low+1)>>1));
  101. 			if(prev_mid==mid)mid--;
  102. 			if(mid>k)high=mid;
  103. 			else if(mid<k)low=mid+1;
  104. 			else return a[mid];
  105. 			prev_mid=mid;
  106. 		}
  107. 		return a[low];
  108. 	}
  109. 	public static Object binarySearchCount(Object a[],Object number,int count){
  110. 		int low=0,high=count-1,mid=(low+((high-low+1)>>1));
  111. 		while(low<high){
  112. 			mid=(low+((high-low+1)>>1));
  113. 			if((Integer)a[mid]>(Integer)number)high=mid-1;
  114. 			else if((Integer)a[mid]<(Integer)number)low=mid;
  115. 			else return mid==0?1:mid+1;
  116. 		}
  117. 		if(low==0 && (Integer)a[low]<=(Integer)number)return 1;
  118. 		else if(low==0 && (Integer)a[low]>(Integer)number)return 0;
  119. 		return low+1;
  120. 	}
  121.  
  122. static class Reader {
  123. 	final private int BUFFER_SIZE = 1 << 16;
  124. 	private DataInputStream din;
  125. 	private byte[] buffer;
  126. 	private int bufferPointer, bytesRead;
  127.  
  128. 	public Reader() {
  129. 		din = new DataInputStream(System.in);
  130. 		buffer = new byte[BUFFER_SIZE];
  131. 		bufferPointer = bytesRead = 0;
  132. 	}
  133.  
  134. 	public Reader(String file_name) throws IOException {
  135. 		din = new DataInputStream(new FileInputStream(file_name));
  136. 		buffer = new byte[BUFFER_SIZE];
  137. 		bufferPointer = bytesRead = 0;
  138. 	}
  139.  
  140. 	public String readLine() throws IOException {
  141. 		byte[] buf = new byte[64];
  142. 		int cnt = 0, c;
  143. 		while ((c = read()) != -1) {
  144. 			if (c == '\n')
  145. 				break;
  146. 			buf[cnt++] = (byte) c;
  147. 		}
  148. 		return new String(buf, 0, cnt);
  149. 	}
  150.  
  151. 	public int nextInt() throws IOException {
  152. 		int ret = 0;
  153. 		byte c = read();
  154. 		while (c <= ' ')
  155. 			c = read();
  156. 		boolean neg = (c == '-');
  157. 		if (neg)
  158. 			c = read();
  159. 		do {
  160. 			ret = ret * 10 + c - '0';
  161. 		} while ((c = read()) >= '0' && c <= '9');
  162. 		if (neg)
  163. 			return -ret;
  164. 		return ret;
  165. 	}
  166.  
  167. 	public long nextLong() throws IOException {
  168. 		long ret = 0;
  169. 		byte c = read();
  170. 		while (c <= ' ')
  171. 			c = read();
  172. 		boolean neg = (c == '-');
  173. 		if (neg)
  174. 			c = read();
  175. 		do {
  176. 			ret = ret * 10 + c - '0';
  177. 		} while ((c = read()) >= '0' && c <= '9');
  178. 		if (neg)
  179. 			return -ret;
  180. 		return ret;
  181. 	}
  182.  
  183. 	public double nextDouble() throws IOException {
  184. 		double ret = 0, div = 1;
  185. 		byte c = read();
  186. 		while (c <= ' ')
  187. 			c = read();
  188. 		boolean neg = (c == '-');
  189. 		if (neg)
  190. 			c = read();
  191. 		do {
  192. 			ret = ret * 10 + c - '0';
  193. 		} while ((c = read()) >= '0' && c <= '9');
  194. 		if (c == '.')
  195. 			while ((c = read()) >= '0' && c <= '9')
  196. 				ret += (c - '0') / (div *= 10);
  197. 		if (neg)
  198. 			return -ret;
  199. 		return ret;
  200. 	}
  201.  
  202. 	private void fillBuffer() throws IOException {
  203. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  204. 		if (bytesRead == -1)
  205. 			buffer[0] = -1;
  206. 	}
  207.  
  208. 	private byte read() throws IOException {
  209. 		if (bufferPointer == bytesRead)
  210. 			fillBuffer();
  211. 		return buffer[bufferPointer++];
  212. 	}
  213.  
  214. 	public void close() throws IOException {
  215. 		if (din == null)
  216. 			return;
  217. 		din.close();
  218. 	}
  219. }
  220.  
  221. }
  222.  
Success #stdin #stdout 0.12s 380672KB
comments (?)
stdin
copy 
1000
I 4220
I 42
K 74419
I 54
I 1241
I 1
I 1
I 3
I 207
I 170154
K 7
I 10791
I 4
I 32
I 5463540
I 235
I 47
I 8
I 4
K 248
I 63794
I 16
K 19
I 83
D 5
I 28
I 88
C 308
I 0
I 48
K 1
I 2183
I 39
I 28
K 467159645
I 0
C 6
I 20
I 22
C 4
C 15217947
I 546879
I 710297
I 1416
I 888
I 2
I 1
I 6
I 7535
D 4
K 1664
I 41
I 5717764
C 0
D 1
C 441
I 335
I 4493003
I 1756
K 1
I 495861
I 1
I 29
I 3
D 6
K 5
C 5
I 1
I 2
D 1691
I 3170011
I 16
D 76
D 2
C 5
K 41
K 1
I 427588
I 170
I 245
I 1
I 1
I 1
I 10606
D 5204
D 2
I 3
K 6
K 28224
I 171
I 955
D 1
I 1
K 21
C 4662
I 337
I 5
I 4
D 96
C 309
K 860
D 508256883
I 717
I 604
C 117
I 372126
D 1
I 4
K 8036
I 1
K 326
I 5
C 56750
I 3
I 32211
I 33
I 83
D 6
I 403826
K 40
I 155
I 18
I 563118
I 84
I 0
I 0
I 24
I 654222318
D 169
K 6
C 29
I 819719976
C 1
I 5
K 4
C 1786
I 506523
I 2
D 23
I 151
I 3622
K 7
I 1428
I 5336863
I 16269
K 1976
I 41
I 1301
I 2384
D 907
D 4
I 16026
I 207610946
I 2369
I 5
K 787107
I 584602
D 67
I 733183
C 224096095
I 757242
I 308
C 6331
K 5
D 308393
I 12769419
C 10635
C 23
C 4
C 272
I 44070
D 100676064
I 2
K 1
D 2
I 1
I 28
I 27
D 2574705
I 143
I 2
K 6
C 2
I 2021
I 6
I 199
K 12
D 133
C 12
I 202483
C 1712983
D 18
I 277190
K 1411
I 11
I 184644813
I 307
I 88430
I 6
C 31
D 6
C 44
K 12509
I 22
K 43
I 132190
C 2
D 23
I 2
K 26
I 6
C 55022
C 1563
I 21537332
C 1376705
D 1
K 171
D 5
I 12
I 3322
I 169
K 535250
I 0
D 16
K 249
K 1008
I 2121
I 32
D 5
D 3
C 219412862
I 58474
C 6
I 42
C 34
I 19
D 6
I 308
I 5
I 5
I 8511
I 495979
I 72948
I 2
K 4
D 209
C 6
D 7678
D 1633
K 159
D 157
K 202
D 277
I 9035
I 4
I 2
I 14601
I 14717131
D 7410
I 25
C 3
I 59022
I 361
C 34
C 0
K 46305
I 20
I 48
I 327
I 41
I 16194
D 1324
C 55714
K 1
I 3
K 1931
D 786
K 1
I 591407346
K 5
I 39
K 7
I 78775
I 0
C 37283114
I 6
I 19055474
I 2
K 15
C 289
I 176222
K 260965219
K 27
I 212
C 8141
I 3
C 1
I 19
I 180
C 91074
I 62
K 322
D 33
C 2331749
K 114
K 1
K 37974
I 517
K 147
K 11
I 211
C 813195
I 1
I 14336
K 115
C 44
I 1
I 74774351
I 21
C 1
C 5
C 7
D 117
I 247255079
D 46757
D 1
I 43
C 213
C 4
D 726380
I 2108879
C 0
K 605736
K 5
K 3
C 341
D 101
C 1
I 13446
I 1939
I 5
I 482
I 15
K 13797
I 84564
D 20
I 2
I 2531
I 2469583
I 2027
I 42268
I 2
K 790662531
I 44
I 1548
D 3
I 14277379
I 17
I 5
I 201
K 156
C 2
I 2058
C 19
D 15
C 6
D 284
D 2514057
K 18
K 4
I 21
C 1
K 238
I 3
K 7
D 37
K 1
C 136
D 37
K 1
C 251
I 3
I 7
D 41
C 6
I 31
I 281999047
I 26012
I 2
I 211
I 1
I 92
I 6
C 3271396
K 92
D 6
K 7
I 18
I 1440359
I 5
I 3
I 22
C 5
I 3
D 15094
D 803666
I 0
C 47
C 251
C 3
I 7856
I 3
K 6
I 184
I 69
K 645671
I 0
I 17517281
I 340419
I 182
I 267
K 112274
K 3
I 1789
I 12
I 12261
I 3
I 1094
I 6
I 3
I 34
D 23
I 1
I 10223
K 439706
K 611
I 1
K 4
K 2
K 64523
D 260
I 20
C 3
I 60038
I 14
I 13035
I 2262
C 5
I 479774299
I 5
I 1334
I 2
I 230
C 34
I 307
C 5
C 788
D 38
I 4306604
I 44
I 97601
I 6
I 117
K 5
C 3
I 99286
I 2967356
C 3
I 3
I 246712
K 62
I 35
I 4
I 134
C 39
I 2875
I 2
I 94
C 6169
I 194
I 794590310
K 5820
D 5
I 6
I 4
C 1316
D 4
I 296
I 22
C 1948
I 8
I 4
I 1
D 0
K 144
C 4
I 1
I 1884
D 198260116
I 4
I 3
I 77866875
C 25
C 2
I 0
D 0
I 5
I 4
D 37
C 10950
I 3
I 4
K 144
I 1025
C 0
I 276
C 228568408
K 37
I 116
I 5229468
I 19
I 1751573
I 23341996
I 0
I 3
K 44878
D 13
C 3
I 2
C 41
C 135544817
I 1449
D 892
C 279412471
I 340
I 301
I 2
I 2
D 31
I 4
I 142
D 299
K 12895
I 809
K 2
I 36
I 21
C 458803246
K 10659
I 165131059
I 15
I 30
K 1257
D 9
I 539389430
D 206804381
I 4
C 5638
I 2
D 21736
I 2982
I 3
I 32
K 32
I 241
I 11730
I 11239
I 38
C 6
I 22
I 16
K 5
I 11
C 40232
I 245
I 5513
I 9451
I 254
I 11
D 10501
I 28
I 190305
I 2
C 3
I 41
I 2981106
I 25
I 44
C 1
I 654043
D 566
D 129
I 143014892
I 6
K 283
C 39
I 23
I 5
I 22691043
K 2
I 20
I 4
D 1
I 0
I 2
D 4
C 2
I 3
I 0
D 6
K 207000691
I 749
I 35
K 45616
D 16658931
D 13
C 0
I 0
C 230890156
I 6
D 2207
I 15836
D 232767599
C 7670
C 1631
I 3
K 6344
C 767
I 691762
I 114734
D 3687316
I 234
C 4
I 13626
I 112
I 1919
I 827870067
I 238237751
K 738
C 285
D 10
I 1188
D 47
C 1
I 11
I 3
I 45
I 5
I 244
I 17
I 48
C 0
K 7
I 2
I 60
D 31
I 2
K 48
K 87
I 0
K 144
I 97121
K 333
K 31
D 18
I 122
I 232
I 160775
I 231
I 1
C 3
D 1
I 2170435
K 14729
I 13198
I 5489
I 44
D 0
I 4
I 24
I 14311492
D 11
I 5
I 1849
D 6
C 1320
K 605971
K 589
I 313
I 1690
I 1
D 360
I 2
I 43
K 1139
I 29697226
I 6
I 44
C 3
I 2772
I 1647
I 24
C 2615573
I 313
D 1
C 28689994
I 806711
K 2917907
K 16
I 300674
I 2262
C 48
I 137
C 19
I 6
K 1166
I 720296506
I 2
I 7
I 37
I 26633583
K 203
K 3845
D 4
K 5
I 2
I 43446
C 40
I 0
D 3
I 5
I 4
I 151
C 9590
I 707328
I 5
D 100
K 8707
I 10
C 2
K 630
I 52
D 6
K 798603
I 29
I 3
I 2
I 0
D 0
C 9
I 30015037
I 4
K 9773
K 2
I 47196
I 28
C 201
I 3997315
C 4
C 44
D 30723
I 4
I 330660
K 7516
K 321
K 4
I 209
I 285
I 36
K 1
I 1021
I 2274
K 1907675
C 2183
C 441
C 39
I 920
I 25
K 1627
I 6168
C 20
I 5510956
I 429793640
D 2
K 1738
I 1
D 33
C 309
I 363
D 309
I 4729
I 99910
I 15172
D 1177
I 561895
K 300
D 28349960
D 87
K 4854
I 5
I 19
I 934
C 2
I 2
I 5
I 1008
C 2
I 40
I 5
I 3
I 2
K 264
D 628
I 7361
I 5
I 5
D 6
C 0
I 495
I 35701612
I 4
I 41
K 5863
C 142
I 16452
I 3
D 76
D 2472222
I 461445
D 492497
I 37
I 274
I 41
I 14
I 33198
I 54811
I 10613
I 106761
K 7
I 767039
D 3
I 6
K 3
I 115402
K 30
I 0
I 193
I 46
I 0
I 19
K 4
I 0
D 5
I 124
K 11783
I 1387131
I 4
K 10954
K 252
I 11
I 0
C 1
I 14
K 837003941
I 26
I 12
I 316
D 6
C 8
I 27
I 338
I 4
D 108
D 101
I 6
I 8785
I 5
I 32
I 817
K 6
I 1731
I 6
C 34
I 18073744
I 156
D 1044
I 0
I 0
C 306
I 18158
I 6
K 4
D 2601956
K 2
I 1
I 1206
I 84606
I 14
I 27
D 4
I 0
C 491975
I 1
I 26
I 27
I 4
C 3
I 143553320
C 4
I 25
I 11220
K 2
D 3
I 52730
C 12
I 5
I 2
I 1555
I 3711639
I 1
I 48
I 9583
I 0
K 29
C 263
K 330
I 37
I 1967
D 5
I 3563333
I 319
D 2343
I 4
D 27
I 3
D 43
I 2
I 2268
C 4
K 342
I 1292
C 40456
I 5
K 286427
C 5
K 4
I 229703142
C 24892414
I 1
K 4162
K 18699
D 1
I 43
I 0
D 1116
I 14
C 116958
I 30
I 268
I 4
I 31
I 4
C 42
K 25395401
I 876
C 697378
I 3
I 23
I 4
I 49
D 5001315
I 732674
I 87128656
C 1774
D 30
I 172909172
D 2127
I 0
D 111235
D 3
I 2
I 100
D 34
I 1812851
I 6
K 270727585
K 3
K 26
I 3832802
C 1908
D 5
K 47
I 26900390
I 2223
C 57550
C 39938
I 76
I 10
I 11
I 10690
stdout
copy 
invalid
4220
invalid
invalid
14
0
invalid
4
3
26
invalid
0
20
0
8
4
3
invalid
0
20
invalid
207
31
25
invalid
20
invalid
invalid
39
10791
8
12
1
4
39
8
invalid
invalid
71
48
5
50
10
4
31
0
8
2
24
7
74
invalid
15
19
invalid
1241
2
143
61
47
78
invalid
invalid
invalid
invalid
87
2
14
8
3
invalid
invalid
2
17
0
invalid
70
0
invalid
0
5
11
101
27
38
invalid
84
63
1
80
invalid
97
invalid
0
invalid
invalid
20
99
819719976
22
1
5
7
41
3
0
invalid
5
3
48
1
invalid
invalid
invalid
1
10
4
32
5
1
invalid
8
0
31
0
45
5
120
42268
7
5
26
48
3
5
invalid
invalid
2
invalid
invalid
3
1
invalid
3
5
25
5
67
4
3
3
335
27
96
invalid
76
83
757242
3
17
1
105
710297
0
168
84
invalid
3
28
171
175
invalid
1
180
invalid
invalid
109
43
6
4
132
3
1
invalid
31
1
1
invalid
invalid
0
195
117
97
invalid
85
3
invalid
73
1
0
8
116
604
32211
invalid
39
3
invalid
97
invalid
invalid
invalid
2
195
212
invalid
22
34
12
invalid
4493003
invalid
7
29
136
invalid
1
invalid
invalid
6
invalid
3
64
2
33
invalid
invalid
5
2
invalid
122
91
29
invalid
13
invalid
85
invalid
invalid
1
1
invalid
0
invalid
54
8
4
38
4
invalid
invalid
22691043
1
invalid
5
6
28
93
4
1
223
3
3
1
10
34
87
invalid
4
invalid
193
invalid
5
3
275
invalid
invalid
216
36
invalid
243
139
invalid
4
32
140
88
202
196
https://ideone.com/IVQVfc
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
secret

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!