Elearning CodePath – CTP Online Judge

Thời điểm Giá trị về 0

BS015

🟢 Hard #Binary Search #Segment Tree #Combinatorics #Interval

### 📌 Thông tin chung

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

Cho một mảng $A$ gồm $N$ số nguyên dương. Ta thực hiện $M$ thao tác, mỗi thao tác có dạng:
* Chọn ra một đoạn $[L, R]$ rồi trừ đi tất cả các phần tử trong đoạn $[L, R]$ cho $S$.

Yêu cầu: Với mỗi vị trí $i$ ($1 \le i \le N$), hãy xác định thời điểm thao tác đầu tiên mà giá trị $A[i] \le 0$.

Nếu không tồn tại thời điểm $A[i] \le 0$ sau $M$ thao tác, in ra $-1$.

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

* Dòng đầu tiên: Gồm $N$ (số phần tử) và $M$ (số thao tác).
* Dòng tiếp theo: Gồm $N$ số nguyên $A[i]$ là giá trị ban đầu của mảng.
* $M$ dòng tiếp theo: Mỗi dòng gồm 3 số nguyên $L, R, S$ mô tả một thao tác.

Giới hạn:
* $N, M \le 10^6$.
* $1 \le A[i] \le 10^9$.
* $L \le R \le N, S \le 10^9$.

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

Gồm $N$ số nguyên, mỗi số nguyên ghi nhận thời điểm đầu tiên mà giá trị $A[i] \le 0$. Các số cách nhau bởi dấu cách.

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `8 7` `4 5 2 2 9 6 2 8` `5 8 3` `5 7 4` `3 4 1` `2 2 4` `2 4 2` `8 8 9` `2 7 5` | `-1 6 5 6 7 2 1 6` |

Giải thích (Theo chỉ số của các thao tác):
* $i=1$: $A[1]=4$. Không bị trừ lần nào. $4 > 0$. Output: **-1**.
* $i=7$: $A[7]=2$.
    * Thao tác 7: $[2, 7]$ trừ 5. $A[7] \leftarrow 2 - 5 = -3 \le 0$. Thời điểm đầu tiên là **7**.
* $i=8$: $A[8]=8$.
    * Thao tác 1: $[5, 8]$ trừ 3. $A[8] \leftarrow 8 - 3 = 5$.
    * Thao tác 6: $[8, 8]$ trừ 9. $A[8] \leftarrow 5 - 9 = -4 \le 0$. Thời điểm đầu tiên là **6**.

---
### 🏷 Ràng buộc

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- | 
| $1$ | $N, M \le 1000$ | $O(N \cdot M)$ | $30\%$ |
| $2$ | $N, M \le 10^5$ | $40\%$ |
| $3$ | $N, M \le 10^6$ | $30\%$ |

---

✅ Đã AC: 2 / 7 submissions