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 Ai and a TCHS 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
2156 1789 
862 700 
1106 1041 
1568 1557 
2575 1984 
1033 950 
1738 1649 
1097 1089 
1774 1630 

Sample Output

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 27, 2009
Author: bbi5291

Languages Allowed:

Comments (Search)

Is possible to solve this problem using DP?

Can I have a hint as to why I'm getting SIGABRT? Thanks!

It seems that this
const int MAXN = 3*1e5+2;
is illegal in PEG judges for some reason.

Edit: Thanks.

is not the same as

i thought u said scores are from 1 to 100000 inclusive.... but apparently there is 0 in the first two test cases, which was funny how i got TLE for the first two cases xD

For some reason my binary tree keeps on resetting itself after the insertion procedure. How do I stop this?

I keep on getting General Protection Fault and some Run-time 216. Does anyone know what that means?

RE 216 is GPE. As stated from Free Pascal:
216 General Protection fault
The application tried to access invalid
memory space. This can be caused by
several problems:
-Dereferencing a nil pointer
-Trying to access memory which is out of
bounds (for example, calling move with
an invalid length).

Use a binary search tree or binary indexed tree.

Did you not bother to read the problem statement?
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.

Note that for a given pair of coders, it is possible that neither is better than the other. There is nothing unusual about this.