Chạy Bộ (Gold)

Đ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ò chạy bộ trên đường thẳng vô hạn, mỗi con có vị trí xuất phát phân biệt và vận tốc riêng. Đường chạy có nhiều làn đường song song. Quy tắc: hai con bò ở cùng một làn đường không được ở cùng vị trí tại bất kỳ thời điểm nào trong khoảng $[0, T]$ (tính cả thời điểm $T$ ).

Hỏi cần ít nhất bao nhiêu làn đường?

Dữ liệu vào

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

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

Dữ liệu ra

Một số nguyên — số làn đường tối thiểu cần dùng.

Ràng buộc

$1 \leq N \leq 100 000$
$1 \leq T \leq 10^{9}$
$0 \leq p_{i}, 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 3 0 1 1 2 2 3 3 2 6 1	3	proj = [3,7,11,9,9]. Dãy dài nhất không tăng: [11,9,9] → 3 làn.
4 0 1 5 2 3 3 1 4 2	1	T=0: proj = vị trí = [1,2,3,4] (tăng nghiêm ngặt). Dãy không tăng dài nhất = 1 → chỉ cần 1 làn.

Bình luận

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