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.Comparator;
  7.  
  8.  
  9. class RATING {
  10. static int tree[];
  11. 	public static void main(String[] args) throws IOException {
  12. 		// TODO Auto-generated method stub
  13. Reader r=new Reader();
  14. StringBuilder sb=new StringBuilder();
  15. PrintWriter pr=new PrintWriter(System.out);
  16. int n=r.nextInt();
  17. Pair p[]=new Pair[n+1];
  18. Pair p2[]=new Pair[n+1];
  19. tree=new int[100001];
  20. p[0]=new Pair(0, 0, 0);
  21. p2[0]=new Pair(0, 0, 0);
  22. for(int i=1;i<=n;i++){
  23. 	p[i]=new Pair(i,r.nextInt(),r.nextInt());
  24. 	p2[i]=new Pair(i,p[i].rating2,p[i].rating1);
  25. 	update(p[i].rating2,1);
  26. }
  27. Arrays.sort(p);
  28. Arrays.sort(p2,new Comparator<Pair>() {
  29. 	@Override
  30. 	public int compare(Pair o1, Pair o2) {
  31. 		// TODO Auto-generated method stub
  32. 		if(o1.rating1==o2.rating1)return o1.rating2-o2.rating2;
  33. 		return o1.rating1-o2.rating1;
  34. 	}
  35. });
  36. //System.out.println(Arrays.toString(p));
  37. //System.out.println(Arrays.toString(p2));
  38. int answers[]=new int[n+1];
  39. for(int i=p.length-1;i>0;i--){
  40. 	int sum=read(p[i].rating2-1);
  41. 	int sub=0;
  42. 	int count=0;
  43. 	//if(count==0)
  44. 		 sub=binarySearch(p2,p[i].rating2,p[i].index);
  45. 	if(sum==0){
  46. 	for(int j=i-1;j>0;j--){
  47. 		if(p[i].rating1>p[j].rating1)break;
  48. 		count++;
  49. 	}
  50. 	}
  51. //	System.out.println(i+" "+sub);
  52. 	//else
  53. 		answers[p[i].index]=sum+sub-count;
  54. 	//sb.append(sum+"\n");
  55. 	update(p[i].rating2,-1);
  56. }
  57. for(int i=1;i<=n;i++)sb.append(answers[i]+"\n");
  58. pr.write(sb.toString());
  59. pr.flush();
  60.  
  61. 	}
  62. 	public static int binarySearch(Pair p2[],int val,int index){
  63. 		int low=1,high=p2.length-1,mid=(low+((high-low+1)>>1));
  64. 		while(low<high){
  65. 			mid=(low+((high-low+1)>>1));
  66. 			if(p2[mid].rating1<val)low=mid+1;
  67. 			else if(p2[mid].rating1==val){
  68. 				low=mid;
  69. 				}
  70. 			else high=mid-1;
  71. 		}
  72. 		if(p2[low].index==index){
  73. 			int count=0;
  74. 			for(int j=low-1;j>0 && p2[j].rating1==val;j--)
  75. 				count++;
  76. 			return count;
  77. 		}
  78. 		else{
  79. 			int j=low-1,count=0;
  80. 			for(;j>0 && p2[j].index!=index;j--);
  81. 			for(int k=j-1;k>0 && p2[k].rating1==val;k--)
  82. 				count++;
  83. 			return count;
  84.  
  85. 		}
  86. 	//	return 0;
  87. 	}
  88. 	public static void update(int idx,int value){
  89. 		while(idx<tree.length){
  90. 			tree[idx]+=value;
  91. 			idx += idx & -idx;
  92. 		}
  93. 	}
  94. 	public static int read(int idx){
  95. 		int sum=0;
  96. 		while(idx>0){
  97. 			sum+=tree[idx];
  98. 			idx -=idx & -idx;
  99. 		}
  100. 		return sum;
  101. 	}
  102. 	static class Pair implements Comparable<Pair>{
  103. 		int index,rating1,rating2;
  104.  
  105. 		@Override
  106. 		public String toString() {
  107. 			return "Pair [index=" + index + ", rating1=" + rating1 + ", rating2=" + rating2 + "]\n";
  108. 		}
  109.  
  110. 		public int getIndex() {
  111. 			return index;
  112. 		}
  113.  
  114. 		public void setIndex(int index) {
  115. 			this.index = index;
  116. 		}
  117.  
  118. 		public int getRating1() {
  119. 			return rating1;
  120. 		}
  121.  
  122. 		public void setRating1(int rating1) {
  123. 			this.rating1 = rating1;
  124. 		}
  125.  
  126. 		public int getRating2() {
  127. 			return rating2;
  128. 		}
  129.  
  130. 		public void setRating2(int rating2) {
  131. 			this.rating2 = rating2;
  132. 		}
  133.  
  134. 		public Pair() {
  135. 			super();
  136. 			// TODO Auto-generated constructor stub
  137. 		}
  138.  
  139. 		public Pair(int index, int rating1, int rating2) {
  140. 			super();
  141. 			this.index = index;
  142. 			this.rating1 = rating1;
  143. 			this.rating2 = rating2;
  144. 		}
  145.  
  146. 		@Override
  147. 		public int compareTo(Pair o) {
  148. 			// TODO Auto-generated method stub
  149. 			if(this.rating1==o.rating1)return this.rating2-o.rating2;
  150. 			return this.rating1-o.rating1;
  151. 		}
  152. 	}
  153. static class Reader {
  154. 	final private int BUFFER_SIZE = 1 << 16;
  155. 	private DataInputStream din;
  156. 	private byte[] buffer;
  157. 	private int bufferPointer, bytesRead;
  158.  
  159. 	public Reader() {
  160. 		din = new DataInputStream(System.in);
  161. 		buffer = new byte[BUFFER_SIZE];
  162. 		bufferPointer = bytesRead = 0;
  163. 	}
  164.  
  165. 	public Reader(String file_name) throws IOException {
  166. 		din = new DataInputStream(new FileInputStream(file_name));
  167. 		buffer = new byte[BUFFER_SIZE];
  168. 		bufferPointer = bytesRead = 0;
  169. 	}
  170.  
  171. 	public String readLine() throws IOException {
  172. 		byte[] buf = new byte[64];
  173. 		int cnt = 0, c;
  174. 		while ((c = read()) != -1) {
  175. 			if (c == '\n')
  176. 				break;
  177. 			buf[cnt++] = (byte) c;
  178. 		}
  179. 		return new String(buf, 0, cnt);
  180. 	}
  181.  
  182. 	public int nextInt() throws IOException {
  183. 		int ret = 0;
  184. 		byte c = read();
  185. 		while (c <= ' ')
  186. 			c = read();
  187. 		boolean neg = (c == '-');
  188. 		if (neg)
  189. 			c = read();
  190. 		do {
  191. 			ret = ret * 10 + c - '0';
  192. 		} while ((c = read()) >= '0' && c <= '9');
  193. 		if (neg)
  194. 			return -ret;
  195. 		return ret;
  196. 	}
  197.  
  198. 	public long nextLong() throws IOException {
  199. 		long ret = 0;
  200. 		byte c = read();
  201. 		while (c <= ' ')
  202. 			c = read();
  203. 		boolean neg = (c == '-');
  204. 		if (neg)
  205. 			c = read();
  206. 		do {
  207. 			ret = ret * 10 + c - '0';
  208. 		} while ((c = read()) >= '0' && c <= '9');
  209. 		if (neg)
  210. 			return -ret;
  211. 		return ret;
  212. 	}
  213.  
  214. 	public double nextDouble() throws IOException {
  215. 		double ret = 0, div = 1;
  216. 		byte c = read();
  217. 		while (c <= ' ')
  218. 			c = read();
  219. 		boolean neg = (c == '-');
  220. 		if (neg)
  221. 			c = read();
  222. 		do {
  223. 			ret = ret * 10 + c - '0';
  224. 		} while ((c = read()) >= '0' && c <= '9');
  225. 		if (c == '.')
  226. 			while ((c = read()) >= '0' && c <= '9')
  227. 				ret += (c - '0') / (div *= 10);
  228. 		if (neg)
  229. 			return -ret;
  230. 		return ret;
  231. 	}
  232.  
  233. 	private void fillBuffer() throws IOException {
  234. 		bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
  235. 		if (bytesRead == -1)
  236. 			buffer[0] = -1;
  237. 	}
  238.  
  239. 	private byte read() throws IOException {
  240. 		if (bufferPointer == bytesRead)
  241. 			fillBuffer();
  242. 		return buffer[bufferPointer++];
  243. 	}
  244.  
  245. 	public void close() throws IOException {
  246. 		if (din == null)
  247. 			return;
  248. 		din.close();
  249. 	}
  250. }
  251.  
  252. }
  253. /*
  254. [Pair [index=0, rating1=0, rating2=0]
  255. , Pair [index=2, rating1=862, rating2=700]
  256. , Pair [index=8, rating1=1014, rating2=1473]
  257. , Pair [index=6, rating1=1033, rating2=950]
  258. , Pair [index=3, rating1=1075, rating2=1089]
  259. , Pair [index=4, rating1=1568, rating2=1557]
  260. , Pair [index=7, rating1=1656, rating2=1649]
  261. , Pair [index=1, rating1=1798, rating2=1832]
  262. , Pair [index=5, rating1=2575, rating2=1984]
  263. ]
  264. */
  265. /*
  266. 8
  267. 862 700
  268. 1014 1473
  269. 1033 600
  270. 1075 1475
  271. 1568 650
  272. 1656 1474
  273. 1798 1473
  274. 2575 1475
  275. */
  276. /*
  277. 9
  278. 862 100
  279. 1014 100
  280. 1033 100
  281. 1075 200
  282. 1568 300
  283. 1656 200
  284. 1798 300
  285. 2575 300
  286. 2600 200
  287. */
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
9
100 862
100 1014
100 1033
1075 200
300 1568
200 1656
200 2600
300 2575
300 1798
stdout
copy 
0
1
2
0
3
3
4
6
5
https://ideone.com/5ZUP5a
language:
Java (12.0.1)
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!