RATING - Coder Ratings

Some of the more elite (and not-so-elite) coders around take part in a certain unnamed programming contest. In said contest, there are multiple types of competitions. Here, we consider the Open and High School competition types. For each type, each competitor receives a rating, an integer between 1 and 100000, inclusive. A coder's rating is based upon his or her level of performance in matches and is calculated using a complicated formula which, thankfully, you will not be asked to implement.

Although the Open and High School ratings for a coder who has participated in both competition types lately are usually close, this is not always the case. In particular, High School matches are more about speed, since many coders are able to solve all the problems, whereas Open matches require more thinking and there is a steeper curve in terms of problem difficulty.

Problem Statement
You are given N coders (1 ≤ N ≤ 300000), conveniently numbered from 1 to N. Each of these coders participates in both High School and Open matches. For each coder, you are also given an Open rating Ai and a High School rating Hi. Coder i is said to be better than coder j if and only if both of coder i's ratings are greater than or equal to coder j's corresponding ratings, with at least one being greater. For each coder i, determine how many coders coder i is better than.

Input Format
On the first line of input is a single integer N, as described above.
N lines then follow. Line i+1 contains two space-separated integers, Ai and Hi.

Output Format
Line i should contain the number of coders that coder i is better than.

Sample Input

8
1798 1832
862 700
1075 1089
1568 1557
2575 1984
1033 950
1656 1649
1014 1473

 

Sample Output

6
0
2
4
7
1
5
1

 


Added by:Brian Bi
Date:2009-04-10
Time limit:1s-1.846s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:own problem

hide comments
2021-01-26 20:51:54
It seems like ratings are larger than 100000. Use 300000 as max
2020-05-24 19:20:16
Just easy fenwick tree
2020-05-24 19:19:25
Easy :) I get AC.
2020-05-22 08:58:55
Use Fast Output For Java
2019-12-25 18:08:05
Nice problem take care about the same rated guys :)
2018-10-23 10:58:01
can anyone please post the solution .please
2018-09-27 19:48:19
Time Limit Exceeded in java
2018-07-18 08:29:56
Nice Problem !!
Use vector of pairs for easy implementation.
2017-12-21 10:57:12
Those who are getting WA on 9th testcase, check for the below testcase ::
17
1798 1832
862 700
1075 1089
1048 1089
888 700
862 770
1568 1557
15445 45464
1568 1557
1033 950
145 950
1014 1473
1011 1473
2575 1984
1033 950
1656 1649
1014 1473
Ans ::
14
0
7
6
1
1
11
16
11
4
0
5
4
15
4
13
5
2017-06-24 23:32:12
Easy :)
but take care of this statement "or equal to coder j's corresponding ratings, with at least one being greater"
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.