| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P152SUMB - ROUND 2B - Nhà an toàn |
Hà Nội mùa này có gió rất to, những dãy nhà ở Hà Nội có nguy cơ bị gió thổi đổ bất cứ lúc nào. Hôm nay TungND đi tán gái về muộn thì gặp ngay cơn bão về, nếu tiếp tục ở ngoài đường thì kiểu gì cũng sẽ bị gió thổi bay, chính vì thế TungND muốn tìm một nhà để trú nhờ.
Ta coi các ngôi nhà ở Hà Nội có tọa độ là x[i] và có chiều cao là h[i].
Ngôi nhà thứ i được gọi là an toàn khi đoạn [x[i] – d, x[i]) có ít nhất một tòa nhà thỏa mãn h[j] >= 2 * h[i], tương tự với đoạn (x[i], x[i] + d ], với d được gọi là khoảng cách an toàn.
Bạn hãy đếm giúp TungND xem có bao nhiêu căn nhà an toàn mà anh có thể tránh gió được.
Input
Dòng đầu tiên chứa 2 số nguyên N và d (1 <= N <= 50.000, 1 <= d <= 10^9).
N dòng sau, mỗi dòng là 2 số nguyên x(i) và h(i) tương ứng là vị trí và chiều cao ngôi nhà thứ i (1 <= x[i], h[i] <= 10^9).
Output
In ra đáp án của bài toán.
Example
Input:6 4
10 3
6 2
5 3
9 7
3 6
11 2
Output: 2
Giải thích: Căn nhà có tọa độ 5 và 6 là an toàn.
| Được gửi lên bởi: | adm |
| Ngày: | 2015-07-08 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
