RATING  Coder Ratings
Some of the more elite (and notsoelite) 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 A_{i} and a High School 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 spaceseparated integers, A_{i} and H_{i}.
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
hide comments
~neo~:
20110117 20:11:14
Last edit: 20110819 18:39:31 

.::Manish Kumar::.:
20100921 21:23:36
O(n^2) does not get AC. 

Brian Bi:
20091213 18:54:23
Sure it can, but most people used a data structure that's even faster and easier to code. 

Robert Gerbicz:
20091213 18:54:23
0


მარი:
20091213 18:54:23
If the testcase is


Phạm Lê Quang:
20091213 18:54:23
@Critical Thinking: We don't need Binary Search to solve this problem. 

SALVO:
20091213 18:54:23
@ Critical Thinking... will learn n try :P Last edit: 20090413 19:14:28 

Brian Bi:
20091213 18:54:23
I don't know what you need binary search for. Also, the test data is not by any means contrived, so ordinary BSTs should work (I set the time limit liberally for the sake of slower languages.) Of course, BITs are easier to code and faster besides. Last edit: 20090413 03:08:41 

~!(*(@*!@^&:
20091213 18:54:23
@SALVO : Follow me, it requires some knowledge about interval/segment tree or binary index tree + binary search to AC it.

Added by:  Brian Bi 
Date:  20090410 
Time limit:  0.176s1.846s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET 
Resource:  own problem 