## TC

Some of the more elite (and not-so-elite) coders around take part in a contest called TC. In TC, there are multiple types of competitions. Here, we consider the Algorithm and TCHS 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

*single round matches*(SRMs) and is calculated using a complicated formula.

Each SRM has three problems, usually called the 250, 500, and 1000 because of their most frequently occurring point values, although they can sometimes have slightly different values, such as 300, 550, and 900. In Algorithm SRMs, the 250 is usually fairly easy, the 500 requires some thought, and can be quite difficult, and the 1000 is usually very difficult, accessible only to those with an advanced knowledge of algorithms and well-honed problem-solving skills. In TCHS SRMs, in which only high school students are allowed to participate, the 250 and 500 are usually fairly easy, and the 1000 is most often not harder than an average problem from a typical national olympiad contest.

The interesting thing is that there's a speed factor too - a coder gets no points for a solution if it is even slightly wrong (i.e. does not pass all of the test cases). Instead, partial scoring is based upon the time taken for a coder to submit his or her final solution for that problem. A coder who solves the 250 and 500 quickly may earn more points than a coder who solves only the 1000, but takes a long time to do so.

Although the TCHS and Algorithm ratings for a coder who has participated in both TCHS and Algorithm SRMs lately are usually close, this is not always the case. In particular, TCHS is more about speed, since many coders are able to solve all three problems, whereas Algorithm SRMs 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 TCHS and Algorithm contests. For each coder, you are also given an Algorithm rating

*A*

_{i}and a TCHS rating

*H*

_{i}. 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,

*A*

_{i}and

*H*

_{i}.

**Output Format**

Line

*i*should contain the number of coders that coder

*i*is better than.

**Sample Input**

9 2156 1789 862 700 1106 1041 1568 1557 2575 1984 1033 950 1738 1649 1097 1089 1774 1630

**Sample Output**

7 0 2 4 8 1 5 2 5

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 16M

**Added:** Jan 27, 2009

**Author:** bbi5291

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Marko99on Mar 15, 2018 - 5:14:07 pm UTC Hintmagicalsoupon Mar 15, 2018 - 11:27:13 pm UTC Re: HintKiritoon Dec 25, 2016 - 6:03:39 am UTC SIGABRTbobhob314on Sep 30, 2015 - 12:08:19 am UTC SIGSEGVEdit: Thanks.

bbi5291on Sep 30, 2015 - 5:46:18 am UTC Re: SIGSEGVjavicon Apr 06, 2009 - 7:13:08 am UTC mmDanielon Mar 24, 2009 - 9:52:53 pm UTC help?Danielon Mar 17, 2009 - 12:49:09 am UTC help?jargonon Mar 17, 2009 - 1:30:23 am UTC Re: help?bbi5291on Mar 16, 2009 - 8:28:40 pm UTC Hintbbi5291on Jan 28, 2009 - 1:06:22 am UTC Re: clarification?Note that for a given pair of coders, it is possible that neither is better than the other. There is nothing unusual about this.