Bẫy kiện cỏ (Gold)

Điểm: 1,00 (OI)

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

Farmer John đặt $N$ kiện cỏ khô dọc theo một con đường thẳng. Mỗi kiện cỏ có kích thước $S_{j}$ và vị trí $P_{j}$ . Bessie bò không thể đi xuyên qua kiện cỏ, nhưng nếu chạy cùng một hướng được $D$ đơn vị liên tiếp, cô có thể phá vỡ và loại bỏ vĩnh viễn tất cả các kiện cỏ trên đường có kích thước nghiêm ngặt nhỏ hơn $D$ .

Tính tổng độ dài các đoạn đường mà nếu Bessie đứng ở đó, cô không thể thoát ra được hai đầu đường.

Dữ liệu vào

Dòng đầu: số nguyên $N$
$N$ dòng tiếp theo: hai số nguyên $S_{j}$ và $P_{j}$ — kích thước và vị trí của kiện cỏ thứ $j$

Dữ liệu ra

Một số nguyên — tổng độ dài đường bị bẫy.

Ràng buộc

$1 \leq N \leq 100 000$
$1 \leq S_{j}, P_{j} \leq 10^{9}$
Tất cả $P_{j}$ đều phân biệt

Ví dụ

Input	Output	Giải thích
5 8 1 1 4 8 8 7 15 4 20	14	Các kiện cỡ 8 tại vị trí 1 và 8 tạo thành một bẫy. Khoảng cách giữa chúng là 7. Kiện cỡ 1 ở giữa (vị trí 4) bị phá hủy ngay khi Bessie chạy. Tương tự, kiện cỡ 7 tại vị trí 15 và kiện cỡ 8 tại vị trí 8 tạo bẫy với khoảng cách 7. Tổng = 7 + 7 = 14.
31 17 248 20 115 ... 22 35	251

Bình luận

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