Chật chội
Xem dạng PDFĐề bài
Nông dân John có ~N~ con bò sữa (~1 \leq N \leq 50000~) được nuôi trong một cái chuồng một chiều dài. Con bò thứ ~i~ đứng ở vị trí ~x_i~ và có chiều cao là ~h_i~ (~1 \leq x_i, h_i \leq 10^9~).
Một con bò sẽ cảm thấy "chật chội" nếu như có ít nhất một con bò khác có chiều cao lớn hơn hoặc bằng hai lần chiều cao của nó nằm trong khoảng cách ~D~ về bên trái và có ít nhất một con bò nữa có chiều cao lớn hơn hoặc bằng hai lần nó nằm trong khoảng cách ~D~ về bên phải (~1 \leq D \leq 10^9~).
Những con bò cảm thấy "chật chội" sẽ cho ra rất ít sữa. Chính vì vậy mà FJ muốn biết có bao nhiêu con bò cảm thấy "chật chội". Viết chương trình thực hiện điều này.
Input
Dữ liệu vào từ file văn bản CROWDED.INP:
- Dòng đầu tiên chứa hai số nguyên ~N~ và ~D~.
- ~N~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i, h_i~ lần lượt là vị trí đứng và chiều cao của con bò thứ ~i~.
Output
Ghi ra file văn bản CROWDED.OUT một số nguyên duy nhất là số lượng con bò cảm thấy "chật chội".
Ví dụ
Sample Input
6 4
10 3
6 2
5 3
9 7
3 6
11 2
Sample Output
2
Giới hạn
- Thời gian: ~1.0s~
- Bộ nhớ: ~256MB~
Bình luận