Nested Segments
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
You are given n segments on a line. There are no ends of some segments that coincide. For each segment find the number of segments it contains.
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.
Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.
Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.
Input
The first line contains a single integer n (1 ≤ n ≤ 2·105) — the number of segments on a line.
Each of the next n lines contains two integers li and ri ( - 109 ≤ li < ri ≤ 109) — the coordinates of the left and the right ends of the i-th segment. It is guaranteed that there are no ends of some segments that coincide.
Output
Print n lines. The j-th of them should contain the only integer aj — the number of segments contained in the j-th segment.
4
1 8
2 3
4 7
5 6
3
3 4
1 5
2 6
3
0
1
0
0
1
1
20231128集训
- Status
- Done
- Rule
- IOI
- Problem
- 6
- Start at
- 2023-11-28 19:00
- End at
- 2023-11-28 21:19
- Duration
- 2.3 hour(s)
- Host
-
SamuelXuch
- Partic.
- 15