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
mestu_paul: 2021-07-31 19:51:27

using fenwick tree and value compressing got AC

Felipe Getúlio: 2018-08-19 16:51:59

what is the obvious optimization?

pran4798: 2017-04-07 21:47:03

how we can use bitmask, please give me some hint.

VV: 2013-05-21 16:49:04

No kind of weird optimization required for this problem! Got AC in first try. Just do the obvious optimization.

Last edit: 2013-05-21 17:29:07
Pushkar Mishra: 2013-05-06 03:02:26

No IO optimizations required. Just avoid maps, and other predefined containers or classes.

Robin Lee: 2011-08-30 00:37:44

Writing solution: Fun.
Optimizing solution: Not fun.

Last edit: 2011-08-30 23:02:21
Ashish Massand: 2011-06-21 07:18:19

Got it forgot the fact that the interval shouldn't cover the interval that covers it.

Ashish Massand: 2011-06-21 07:17:40

Could someone explain the second test case. Shouldn't the answer be
1 1

:D: 2011-01-11 11:23:04

You probably can get away with standard I/O but it is highly dependent on implementation details. I would suggest doing both fast 'I' and 'O' :)

~!(*(@*!@^&: 2010-04-15 21:35:07

i dont use fast IO but I need to use C++ 4.3.2


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