풀 구간

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

요약

N개의 구간이 주어질 때, 각 구간 i마다 k_i 이상 겹치는 다른 구간의 개수를 구합니다.

난이도: 보통10점 중 7점
유형: 구간, 정렬, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

베시는 양의 실수 직선 위에 풀을 심는다. $N$ ( $2\le N\le 2\cdot 10^5$ )개의 서로 다른 풀 품종이 있으며, $i$ 번째 품종은 구간 $[\ell_i, r_i]$ ( $0 < \ell_i < r_i \le 10^9$ )에 심는다.

또한 품종 $i$ 는 다른 품종 $j$ ( $j\neq i$ ) 중에 품종 $j$ 와 품종 $i$ 가 길이 $k_i$ 이상으로 겹치는 품종이 있으면 더 잘 자란다. ( $0 < k_i \le r_i - \ell_i$ ) 베시는 모든 품종을 평가하려고 한다. 각 $i$ 에 대해, 품종 $j$ 와 $i$ 가 길이 $k_i$ 이상으로 겹치는 $j\neq i$ 의 개수를 구하라.

입력

첫 줄에 $N$ 이 주어진다.

다음 $N$ 개의 줄에는 각각 공백으로 구분된 세 정수 $\ell_i$ , $r_i$ , $k_i$ 가 주어진다.

출력

모든 품종의 답을 한 줄에 하나씩 출력한다.

예제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

입력

예상 출력