💻
Elearning
CodePath
Problems
Contests
Roadmap
🔐 Login
Thời điểm Giá trị về 0
BS015
### 📌 Thông tin chung | Mục | Chi tiết | | :--- | :--- | | **Tên File Input** | `FIRSTZERO.INP` | | **Tên File Output** | `FIRSTZERO.OUT` | --- ### 📝 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` <br> `4 5 2 2 9 6 2 8` <br> `5 8 3` <br> `5 7 4` <br> `3 4 1` <br> `2 2 4` <br> `2 4 2` <br> `8 8 9` <br> `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: 1 / 5 submissions
⬅ Contest
🚀 Nộp bài
💡 Gợi ý AI
📌 Bài kế
📋 Copy đề
⚙️
⬅ Contest
🚀 Nộp bài
💡 Gợi ý
📌 Bài kế
📋 Copy
📖 Hướng dẫn học tập
Học trò tri ân
☕ Một ly cà phê sẻ chia
Bạn bè ủng hộ
🍜 Một bát phở ấm lòng
💳 Quét mã ủng hộ tuỳ tâm nhé!
💬 Liên hệ Zalo!
Đóng