Grass Segments

시간 제한2초메모리 제한1024 MB

요약

각 구간 i에 대해, 길이가 k_i 이상 겹치는 다른 구간의 개수를 센다.

난이도: 보통10점 중 7점
유형: 정렬, 이분 탐색, 구간
정답자: 아직 제출이 없습니다

문제

Bessie is planting some grass on the positive real line. She has $N$ ( $2\le N\le 2\cdot 10^5$ ) different cultivars of grass, and will plant the $i$ th cultivar on the interval $\[\ell\_i, r\_i]$ ( $0 < \ell\_i < r\_i \leq 10^9$ ).

In addition, cultivar $i$ grows better when there is some cultivar $j$ ( $j\neq i$ ) such that cultivar $j$ and cultivar $i$ overlap with length at least $k\_i$ ( $0 < k\_i \leq r\_i - \ell\_i$ ). Bessie wants to evaluate all of her cultivars. For each $i$ , compute the number of $j\neq i$ such that $j$ and $i$ overlap with length at least $k\_i$ .

입력

The first line contains $N$ .

The next $N$ lines each contain three space-separated integers $\ell\_i$ , $r\_i$ , and $k\_i$ .

출력

The answers for all cultivars on separate lines.

예제3

예제 1
입력
```
2
3 6 3
4 7 2
```
예상 출력
```
0
1
```
예제 2
입력
```
4
3 6 1
2 5 1
4 10 1
1 4 1
```
예상 출력
```
3
3
2
2
```

예제 3

입력

예상 출력