Chạy Bộ (Bronze)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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ò chạy bộ trên một đường thẳng vô hạn, mỗi con ở một vị trí phân biệt và chạy với tốc độ nhất định. Khi một con bò nhanh đuổi kịp con bò chậm phía trước, nó phải giảm tốc và chạy cùng nhóm.

Hãy đếm số nhóm còn lại sau khi tất cả các lần nhập nhóm đã xảy ra.

Dữ liệu vào

Dòng đầu chứa số nguyên $N$ .

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $p_{i}$ và $s_{i}$ — vị trí và tốc độ của con bò thứ $i$ . Các con bò được cho theo thứ tự tăng dần vị trí.

Dữ liệu ra

Một số nguyên duy nhất — số nhóm còn lại.

Ràng buộc

$1 \leq N \leq 100 000$
$0 \leq p_{i} \leq 10^{9}$
$1 \leq s_{i} \leq 10^{9}$
Các vị trí phân biệt và tăng dần

Ví dụ

Input	Output	Giải thích
5 0 1 1 2 2 3 3 2 6 1	2	Ba con đầu (tốc độ 1, 2, 3) sẽ bị con ở vị trí 3 (tốc độ 2) chặn, tạo thành 1 nhóm. Con ở vị trí 6 (tốc độ 1) chậm nhất, tạo nhóm riêng. Tổng 2 nhóm.

Bình luận

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