Elearning CodePath – CTP Online Judge

DOMINO

🟢 Easy #General #Dynamic Programming #Binary Search

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho $N$ quân Domino được đặt dọc theo một trục số (từ trái sang phải).
Domino thứ $i$ được đặt ở tọa độ $x_i$ và có chiều cao $h_i$.

Quy tắc lây lan:
Nếu một quân Domino ở tọa độ $x$ với chiều cao $h$ bị đổ về bên phải, thì nó sẽ làm cho **tất cả** các Domino khác đặt ở các tọa độ $\text{coord}$ thỏa mãn $x+1 \le \text{coord} \le x+h-1$ bị đổ theo về cùng hướng bên phải.

Yêu cầu: Với mỗi Domino thứ $i$ bị Vasya làm đổ ban đầu về bên phải, hãy xác định số lượng $z_i$ các Domino **tổng cộng** bị đổ (bao gồm cả chính nó).

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `DOMINO.INP`:

* Dòng 1: Số nguyên dương $N$.
* $N$ dòng tiếp theo: Dòng thứ $i$ chứa hai số nguyên $x_i$ và $h_i$ là tọa độ và độ cao của Domino thứ $i$.

Giới hạn:
* $1 \le N \le 10^5$.
* $-10^8 \le x_i \le 10^8$.
* $2 \le h_i \le 10^8$.
* Không có hai Domino nào ở cùng một tọa độ.

---
### 📤 Định dạng Đầu ra

Ghi ra file `DOMINO.OUT` trên một dòng $N$ số $z_i$ tìm được, các số ghi ngăn cách nhau bởi một dấu cách.

---
### ✨ Ví dụ

| Input (`DOMINO.INP`) | Output (`DOMINO.OUT`) |
| :--- | :--- |
| `4` <br> `16 5` <br> `20 5` <br> `10 10` <br> `18 2` | `3 1 4 1` |

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 5000$ | $40\%$ |
| 2 | $N \le 10^5$ | $60\%$ |

---

✅ Đã AC: 0 / 1 submissions