Đoạn Cỏ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie trồng $N$ giống cỏ ( $2 \leq N \leq 2 \times 10^{5}$ ) trên trục số thực dương. Giống thứ $i$ được trồng trên đoạn $[ℓ_{i}, r_{i}]$ .

Giống $i$ phát triển tốt hơn khi tồn tại giống $j$ ( $j \neq i$ ) sao cho đoạn giao của $[ℓ_{i}, r_{i}]$ và $[ℓ_{j}, r_{j}]$ có độ dài ít nhất $k_{i}$ .

Với mỗi giống cỏ, hãy đếm có bao nhiêu giống khác thỏa mãn điều kiện trên.

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp: Ba số nguyên $ℓ_{i}$ , $r_{i}$ , $k_{i}$ ( $0 < ℓ_{i} < r_{i} \leq 10^{9}$ , $0 < k_{i} \leq r_{i} - ℓ_{i}$ )

Dữ liệu ra

$N$ dòng, dòng thứ $i$ là số giống cỏ khác thỏa mãn điều kiện giao với giống $i$ .

Ràng buộc

$2 \leq N \leq 2 \times 10^{5}$
$0 < ℓ_{i} < r_{i} \leq 10^{9}$
$0 < k_{i} \leq r_{i} - ℓ_{i}$
Test 4-5: $N \leq 5000$
Test 6-11: $k_{i}$ giống nhau cho mọi $i$

Ví dụ

Input	Output	Giải thích
2 3 6 3 4 7 2	0 1	Đoạn giao $[4, 6]$ có độ dài 2. Đủ cho giống 2 ( $k_{2} = 2$ ) nhưng không đủ cho giống 1 ( $k_{1} = 3$ ).
4 3 6 1 2 5 1 4 10 1 1 4 1	3 3 2 2	Với $k = 1$ , chỉ cần giao tối thiểu 1 đơn vị.

Bình luận

Không có bình luận tại thời điểm này.