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.Arrays;
  6. import java.util.BitSet;
  7. import java.util.HashMap;
  8. //import java.util.Map;
  9.  
  10.  
  11.  
  12.  
  13. class TEMPLEQ {
  14. static int a[];
  15. static BitSet bs;
  16. static int count=0;
  17. 	public static void main(String[] args) throws IOException {
  18. 		// TODO Auto-generated method stub
  19. 		long time=System.currentTimeMillis();
  20. 		Reader r=new Reader();
  21. 		//Reader r=new Reader("/media/ankit/Softwares/ECLIPSE/SPOJ/SPOJ CLASSICAL/src/InputTemple.txt");
  22. int n=r.nextInt();
  23. int q=r.nextInt();
  24. StringBuilder sb=new StringBuilder();
  25. PrintWriter prfile=new PrintWriter(System.out);
  26. //PrintWriter prfile=new PrintWriter("/media/ankit/Softwares/ECLIPSE/SPOJ/SPOJ CLASSICAL/src/OutputTemple.txt");
  27.  a=new int[n+1];
  28. int b[]=new int[n+1];
  29. //segtree=new int[4*n];
  30. bs=new BitSet(n+1);
  31. HashMap<Integer, Integer> hm=new HashMap<Integer, Integer>();
  32. for(int i=1;i<=n;i++){a[i]=r.nextInt();
  33. b[i]=a[i];}
  34. Arrays.sort(a,1,a.length);
  35. for(int i=1;i<=n;i++){
  36. int pos=binarySearch(a, b[i]);
  37. hm.put(i, pos);
  38. }
  39.  
  40. /*for(Map.Entry<Integer, Integer> entry:hm.entrySet()){
  41. System.out.println(entry.getKey()+" "+entry.getValue());
  42. }
  43. */
  44.  
  45.  
  46. for(int i=0;i<q;i++){
  47. 	int choice=r.nextInt();
  48. 	int number=r.nextInt();
  49. 	if(choice==1){
  50.  
  51. 		number=hm.get(number);
  52. 	int	bval=a[number];
  53.  
  54. 		int j=binsearch_rightmost(a, bval, number, a.length-1);
  55.  
  56. 		a[j]++;
  57.  
  58.  
  59. 	}
  60. 	else if(choice==2){
  61. 		int ans=binsearch_leftmost(a,number,1,n);
  62.  
  63. 		if(a[ans]>=number)
  64. 		sb.append((n-ans+1)+"\n");
  65. 		else sb.append((n-ans)+"\n");
  66.  
  67. 	}
  68. 	else
  69. 		{
  70. 		int ans=binsearch_leftmost(a,number,1,n);
  71. 		if(a[ans]>=number)
  72. 		for(int j=ans;j<a.length;++j)a[j]--;
  73. 		}
  74.  
  75. 	//System.out.println(i);
  76. }
  77. 	prfile.write(sb.toString());
  78. 	System.out.println((System.currentTimeMillis()-time)/1000.0);
  79. 	prfile.flush();
  80. 	prfile.close();
  81. 	}
  82. 	public static int binarySearch(int a[],int val){
  83. 		int low=0,high=a.length-1,mid=(low+((high-low+1)>>1));
  84. 		while(low<high){
  85. 			mid=(low+((high-low+1)>>1));
  86. 			if(a[mid]>=val)high=mid-1;
  87. 			else low=mid;
  88. 		}
  89. 		mid=(low+((high-low+1)>>1));
  90. 		if(a[mid]<val){
  91. 			int j;
  92. 			for( j=mid+1;a[j]!=val;j++);
  93. 			mid=j;
  94. 		}
  95. 		if(!bs.get(mid)){
  96. 			bs.set(mid);
  97. 			return mid;
  98. 		}
  99. 		else{
  100. 			int j;
  101. 			for( j=mid;j>0 && a[j]==val && !bs.get(j);j--);
  102. 			if(j!=mid)return j;
  103. 			else{
  104. 				j++;
  105. 				for(;j<a.length && a[j]==val;j++){
  106. 					if(!bs.get(j)){
  107. 						bs.set(j);
  108. 						break;
  109. 					}
  110. 				}
  111. 				return j;
  112. 			}
  113.  
  114. 		}
  115. 	}
  116. 	public static int binsearch_rightmost(int a[],int val,int left,int right){
  117. 		if(left==right)return left;
  118. 		int mid=(left+right+1)>>1;
  119. 			if(a[mid]>val)return binsearch_rightmost(	a, val, left, mid-1);
  120. 			return binsearch_rightmost(a, val, mid, right);
  121. 	}
  122. 	public static int binsearch_leftmost(int a[],int val,int left,int right){
  123. 	    if(left==right) return left;
  124. 	   int mid = (left+right)>>1;
  125. 	    if(a[mid] < val)
  126. 	        return binsearch_leftmost(a,val,mid+1,right);
  127. 	    else
  128. 	        return binsearch_leftmost(a,val,left,mid);
  129. 	}
  130.  
  131. static class Reader {
  132. 	final private int BUFFER_SIZE = 1 << 16;
  133. 	private DataInputStream din;
  134. 	private byte[] buffer;
  135. 	private int bufferPointer, bytesRead;
  136.  
  137. 	public Reader() {
  138. 		din = new DataInputStream(System.in);
  139. 		buffer = new byte[BUFFER_SIZE];
  140. 		bufferPointer = bytesRead = 0;
  141. 	}
  142.  
  143. 	public Reader(String file_name) throws IOException {
  144. 		din = new DataInputStream(new FileInputStream(file_name));
  145. 		buffer = new byte[BUFFER_SIZE];
  146. 		bufferPointer = bytesRead = 0;
  147. 	}
  148.  
  149. 	public String readLine() throws IOException {
  150. 		byte[] buf = new byte[64];
  151. 		int cnt = 0, c;
  152. 		while ((c = read()) != -1) {
  153. 			if (c == '\n')
  154. 				break;
  155. 			buf[cnt++] = (byte) c;
  156. 		}
  157. 		return new String(buf, 0, cnt);
  158. 	}
  159.  
  160. 	public int nextInt() throws IOException {
  161. 		int ret = 0;
  162. 		byte c = read();
  163. 		while (c <= ' ')
  164. 			c = read();
  165. 		boolean neg = (c == '-');
  166. 		if (neg)
  167. 			c = read();
  168. 		do {
  169. 			ret = ret * 10 + c - '0';
  170. 		} while ((c = read()) >= '0' && c <= '9');
  171. 		if (neg)
  172. 			return -ret;
  173. 		return ret;
  174. 	}
  175.  
  176. 	public long nextLong() throws IOException {
  177. 		long ret = 0;
  178. 		byte c = read();
  179. 		while (c <= ' ')
  180. 			c = read();
  181. 		boolean neg = (c == '-');
  182. 		if (neg)
  183. 			c = read();
  184. 		do {
  185. 			ret = ret * 10 + c - '0';
  186. 		} while ((c = read()) >= '0' && c <= '9');
  187. 		if (neg)
  188. 			return -ret;
  189. 		return ret;
  190. 	}
  191.  
  192. 	public double nextDouble() throws IOException {
  193. 		double ret = 0, div = 1;
  194. 		byte c = read();
  195. 		while (c <= ' ')
  196. 			c = read();
  197. 		boolean neg = (c == '-');
  198. 		if (neg)
  199. 			c = read();
  200. 		do {
  201. 			ret = ret * 10 + c - '0';
  202. 		} while ((c = read()) >= '0' && c <= '9');
  203. 		if (c == '.')
  204. 			while ((c = read()) >= '0' && c <= '9')
  205. 				ret += (c - '0') / (div *= 10);
  206. 		if (neg)
  207. 			return -ret;
  208. 		return ret;
  209. 	}
  210.  
  211. 	private void fillBuffer() throws IOException {
  212. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  213. 		if (bytesRead == -1)
  214. 			buffer[0] = -1;
  215. 	}
  216.  
  217. 	private byte read() throws IOException {
  218. 		if (bufferPointer == bytesRead)
  219. 			fillBuffer();
  220. 		return buffer[bufferPointer++];
  221. 	}
  222.  
  223. 	public void close() throws IOException {
  224. 		if (din == null)
  225. 			return;
  226. 		din.close();
  227. 	}
  228. }
  229.  
  230. }
  231. /*
  232. 5 6
  233. 20 30 10 50 40
  234. 2 31
  235. 1 2
  236. 2 31
  237. 3 11
  238. 2 20
  239. 2 50
  240. */
  241. /*
  242. 5 6
  243. 10 10 10 10 10
  244. 1 3
  245. 1 5
  246. 1 3
  247. 3 11
  248. 1 4
  249. 2 11
  250. */
Success #stdin #stdout 0.09s 320256KB
comments (?)
stdin
copy 
5 6
10 10 10 10 10
1 3
1 5
1 3
3 11
1 4
2 11
stdout
copy 
0.002
2
https://ideone.com/0WIYXr
language:
Java (HotSpot 12)
created:
9 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!