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.
|
|
Hemant Verma:
2009-11-21 11:12:06
Yes the Integer will satisfy the limit.
|
|
[Trichromatic] XilinX:
2009-11-21 11:12:06
Will the input parameters satisfy that:
|
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 |