INTERVA2 - Interval Challenge


Give you N (1 <= N <= 200000) intervals, represented as [A, B], for example, interval s represented as [As, Bs].

For two intervals s and t, we say S covered by T if At <= As and Bs <= Bt. Now my problem is easy, just tell me the question below: For each interval, how many intervals can cover it but not covered by it?

Input

The input contains multiple test cases.

For each test case, the first line is an integer N (1 <= N <= 200000), which is the number of intervals. Then come N lines, the i-th of which contains two integers: Ai and Bi (Ai, Bi will not exceed the 32-bit integer) specifying the two parameters described above.

Output

For each test case, output one line containing n space-separated integers, the i-th of which specifying the number of intervals that can cover it but not covered by it.

Example

Input:
3
0 1
-1 2
-2 3
2
0 1
0 1

Output:
2 1 0
0 0

hide comments
P != NP: 2010-03-31 21:49:06

This is too much......It needs IO optimizations to get accepted.....I tried almost 15 times before i got AC.

vYoTo: 2010-03-30 14:11:34

The time limit is too strict for PASCAL.

gaurav jain: 2010-03-28 05:12:16

Can a same Ai Bi pair occur multiple times??

刘启鹏: 2009-11-21 11:12:06

I am puzzle that I still get TLE.
I use O(N)sort , O(NlogN)binary indexed array , quick reading , but it seems not to work at all.
I do not know what to do next.
Please give me some hit :D

Hemant Verma: 2009-11-21 11:12:06

Yes the Integer will satisfy the limit.
And Yes Ai <= Bi . I have used a generator program to generate these , These satisfy the above constraints you mention

[Trichromatic] XilinX: 2009-11-21 11:12:06

Will the input parameters satisfy that:
Ai <= Bi? And will the absolute value of Ai and Bi exceed 231? i.e. Need I use long long int in C/C++?

Edit: The answers are (1)Yes. (2)No. (3)No.

Last edit: 2009-11-15 12:21:27

Added by:Hemant Verma
Date:2009-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Alkhwarizm 2009