Bò chen chúc

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Có $N$ con bò đứng trên một đường thẳng. Con bò thứ $i$ đứng tại vị trí $x_{i}$ và có chiều cao $h_{i}$ .

Một con bò được gọi là "bị chen chúc" nếu tồn tại ít nhất một con bò khác ở bên trái (trong khoảng cách $D$ ) có chiều cao ít nhất gấp đôi chiều cao của nó, VÀ tồn tại ít nhất một con bò khác ở bên phải (trong khoảng cách $D$ ) có chiều cao ít nhất gấp đôi chiều cao của nó.

Cụ thể, con bò tại vị trí $x$ với chiều cao $h$ bị chen chúc khi và chỉ khi:

Tồn tại con bò tại vị trí $x^{'}$ với $x - D \leq x^{'} < x$ và chiều cao $\geq 2 h$ .
Tồn tại con bò tại vị trí $x^{″}$ với $x < x^{″} \leq x + D$ và chiều cao $\geq 2 h$ .

Hãy đếm số con bò bị chen chúc.

Dữ liệu vào

Dòng đầu tiên: hai số nguyên $N$ và $D$ .
$N$ dòng tiếp theo: mỗi dòng chứa hai số nguyên $x_{i}$ và $h_{i}$ .

Dữ liệu ra

Một số nguyên duy nhất: số con bò bị chen chúc.

Ràng buộc

$1 \leq N \leq 50 000$
$1 \leq x_{i}, h_{i} \leq 10^{9}$
$1 \leq D \leq 10^{9}$
Các vị trí $x_{i}$ đôi một khác nhau.

Ví dụ

Input	Output	Giải thích
6 4 10 3 6 2 5 3 9 7 3 6 11 2	2	Sắp xếp theo vị trí: (3,6), (5,3), (6,2), (9,7), (10,3), (11,2). Bò tại x=5 (h=3): bên trái có bò x=3 (h=6 $\geq$ 6), bên phải có bò x=9 (h=7 $\geq$ 6), khoảng cách đều $\leq$ 4. Bò tại x=6 (h=2): bên trái có bò x=3 (h=6 $\geq$ 4), bên phải có bò x=9 (h=7 $\geq$ 4), khoảng cách đều $\leq$ 4. Vậy có 2 bò bị chen chúc.
2 6 97 51 57 85	0	Hai con bò cách nhau 40 > D=6, không con nào bị chen chúc.

Bình luận

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