頁面無法載入？點擊這裡可能會修復。
Placeholder

#8012
子任務

잔디 심기 3s 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


來源

USACO 2024 US Open Gold 2번

需要登入才能撰寫程式碼。