레이팅 미적용설명
베시는 양의 실수 직선 위에 잔디를 심고 있다. 베시에게는 \(N\)(\(2\le N\le 2\cdot 10^5\))가지 서로 다른 잔디 품종이 있으며, \(i\)번째 품종을 구간 \([\ell_i, r_i]\)(\(0 < \ell_i < r_i \leq 10^9\))에 심을 것이다.
또한 품종 \(i\)는, 품종 \(j\)(\(j\neq i\))와 품종 \(i\)가 길이 \(k_i\)(\(0 < k_i \leq r_i - \ell_i\)) 이상 겹치는 어떤 품종 \(j\)가 존재할 때 더 잘 자란다. 베시는 자신의 모든 품종을 평가하고 싶다. 각 \(i\)에 대해, \(j\)와 \(i\)가 길이 \(k_i\) 이상 겹치는 \(j\neq i\)의 개수를 구하여라.
문제 제공: Benjamin Qi
제약
배점
- 입력 4-5: \(N \leq 5000\)
- 입력 6-11: 모든 구간의 \(k\)가 같다
- 입력 12-20: 추가 제약 없음.
또한 입력 5, 7, ..., 19에서는 모든 \(i\)에 대해 \(r_i \leq 2N\)이다.
문제 제공: Benjamin Qi
입력 형식
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에 공백으로 구분된 세 정수 \(\ell_i\), \(r_i\), \(k_i\)가 각각 주어진다.
출력 형식
모든 품종에 대한 답을 한 줄에 하나씩 출력한다.
예제 1
입력
2
3 6 3
4 7 2출력
0
1설명
The overlaps of the cultivars is \([4,6]\), which has length \(2\), which is at
least \(2\) but not at least \(3\).
예제 2
입력
4
3 6 1
2 5 1
4 10 1
1 4 1출력
3
3
2
2예제 3
입력
5
8 10 2
4 9 2
3 7 4
5 7 1
2 7 1출력
0
3
1
3
3문제 정보
태그