ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#2292

[중등부] 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
ログインしないとコードを書けません。