Bắt Táo

Điểm: 1,00 (OI)

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

Táo rơi xuống trục số tại các thời điểm và vị trí cụ thể. Các con bò của Farmer John xuất hiện tại các thời điểm và vị trí cụ thể để bắt táo. Mỗi con bò di chuyển với tốc độ một đơn vị mỗi giây và rời đi sau khi bắt được một quả táo. Quả táo sẽ mất nếu không có bò nào bắt được.

Có $N$ sự kiện ( $1 \leq N \leq 2 \times 10^{5}$ ). Mỗi sự kiện gồm 4 số $q_{i}, t_{i}, x_{i}, n_{i}$ :

Nếu $q_{i} = 1$ : $n_{i}$ con bò xuất hiện tại thời điểm $t_{i}$ , vị trí $x_{i}$
Nếu $q_{i} = 2$ : $n_{i}$ quả táo rơi tại thời điểm $t_{i}$ , vị trí $x_{i}$

Bò ở vị trí $x$ tại thời điểm $t$ có thể bắt táo ở vị trí $x^{'}$ rơi tại thời điểm $t^{'}$ nếu $| x - x^{'} | \leq t^{'} - t$ (với $t^{'} \geq t$ ).

Hãy tìm số táo tối đa có thể bắt được.

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp theo: Bốn số nguyên $q_{i}$ , $t_{i}$ , $x_{i}$ , $n_{i}$

Dữ liệu ra

Một số nguyên duy nhất — số táo tối đa có thể bắt được.

Ràng buộc

$1 \leq N \leq 2 \times 10^{5}$
$q_{i} \in {1, 2}$
$0 \leq t_{i}, x_{i} \leq 10^{9}$
$1 \leq n_{i} \leq 10^{3}$
Tất cả các cặp $(t_{i}, x_{i})$ là phân biệt

Ví dụ

Input	Output	Giải thích
5 2 5 10 100 2 6 0 3 2 8 10 7 1 2 4 5 1 4 7 6	10	5 bò từ sự kiện 4 và 5 bò từ sự kiện 5 có thể bắt tổng cộng 10 quả táo.
5 2 5 10 100 2 6 0 3 2 8 11 7 1 2 4 5 1 4 7 6	9	Thay đổi vị trí táo ở sự kiện 3 làm giảm khả năng tiếp cận, chỉ bắt được 9 quả.

Bình luận

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