페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2293

[고등부] 2024 KOI 2차대회 대비 모의고사 (2주차)

잔디 심기
서브태스크
3초 1024MB

문제

정올이는 N 종류의 잔디 종자를 심으려고 한다. i번째 종자는 구간 [ℓ_i, r_i]에 심을 예정이다.

또한, i번째 종자는 j (j ≠ i) 번째 종자와 적어도 k_i 만큼의 길이로 겹칠 때 더 잘 자란다.

정올이는 각 잔디 종자에 대해 최소 k_i 만큼 겹치는 다른 잔디 종자의 개수가 궁금해졌다.

이를 계산하는 프로그램을 작성하시오.


입력

첫 번째 줄에 정수 N이 주어진다. (2 ≤ N ≤ 200,000)

두 번째 줄부터 N줄에 걸쳐 세 정수 ℓ_i, r_i, k_i가 주어진다. (0 < ℓ_i < r_i ≤ 1,000,000,000, 0 < k_i ≤ r_i - ℓ_i)


출력

N줄에 걸쳐 i번째 줄에 i번째 잔디 종자가 최소 k_i 만큼 겹치는 다른 잔디 종자의 개수를 출력한다.


부분문제

번호 점수 조건
#120점

N \le 5000

#230점

k_i = k_{i+1} (1 \le i \le N-1)

#350점

추가 제한 없음


예제 #1

2
1 4 3
2 5 2
0
1

첫 번째 잔디 종자는 두 번째 잔디 종자와 r_1 - ℓ_2 = 4 - 2 = 2 만큼 겹친다.


예제 #2

4
4 7 1
3 6 1
5 11 1
2 5 1
3
3
2
2

예제 #3

5
9 11 2
5 10 2
4 8 4
6 8 1
3 8 1
0
3
1
3
3

예제 #4

2
0 16 16
1 3 2
0
1
로그인해야 코드를 작성할 수 있어요.