Cô Khong đang chuẩn bị \(n\) hộp kẹo cho học sinh của một ngôi trường gần nhà. Các hộp được đánh số từ \(0\) đến \(n-1\) và ban đầu đều rỗng. Hộp \(i\) (\(0 \le i \le n-1\)) có sức chứa \(c[i]\) viên kẹo.

Cô Khong dành \(q\) ngày để chuẩn bị các hộp kẹo. Vào ngày \(j\) (\(0 \le j \le q-1\)), cô thực hiện một thao tác được xác định bởi ba số nguyên \(l[j]\), \(r[j]\) và \(v[j]\), trong đó \(0 \le l[j] \le r[j] \le n-1\) và \(v[j] \ne 0\). Với mỗi hộp \(k\) thỏa mãn \(l[j] \le k \le r[j]\):

• Nếu \(v[j] > 0\), cô Khong thêm lần lượt từng viên kẹo vào hộp \(k\), cho đến khi đã thêm đúng \(v[j]\) viên kẹo hoặc hộp đầy. Nói cách khác, nếu trước thao tác hộp có \(p\) viên kẹo, thì sau thao tác hộp có số viên kẹo là:

• Nếu \(v[j] < 0\), cô Khong lấy lần lượt từng viên kẹo ra khỏi hộp \(k\), cho đến khi đã lấy ra đúng \(-v[j]\) viên kẹo hoặc hộp rỗng. Nói cách khác, nếu trước thao tác hộp có \(p\) viên kẹo, thì sau thao tác hộp có số viên kẹo là:

Nhiệm vụ của bạn là xác định số kẹo trong mỗi hộp sau \(q\) ngày.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v);

• c: mảng độ dài \(n\). Với \(0 \le i \le n-1\), \(c[i]\) là sức chứa của hộp \(i\).
• l, r, v: ba mảng độ dài \(q\). Vào ngày \(j\), với \(0 \le j \le q-1\), cô Khong thực hiện thao tác được xác định bởi \(l[j]\), \(r[j]\) và \(v[j]\) như mô tả ở trên.
• Hàm phải trả về một mảng \(s\) độ dài \(n\). Với \(0 \le i \le n-1\), \(s[i]\) phải là số kẹo trong hộp \(i\) sau \(q\) ngày.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): \(n\).
• Dòng \(2\): \(c[0]\ c[1]\ \ldots\ c[n-1]\).
• Dòng \(3\): \(q\).
• Dòng \(4+j\) (\(0 \le j \le q-1\)): \(l[j]\ r[j]\ v[j]\).

Dữ liệu ra

Trình chấm mẫu in câu trả lời theo định dạng sau:

• Dòng \(1\): \(s[0]\ s[1]\ \ldots\ s[n-1]\).

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(1 \le q \le 200\,000\).
• \(1 \le c[i] \le 10^9\) với mọi \(0 \le i \le n-1\).
• \(0 \le l[j] \le r[j] \le n-1\) với mọi \(0 \le j \le q-1\).
• \(-10^9 \le v[j] \le 10^9\), \(v[j] \ne 0\) với mọi \(0 \le j \le q-1\).

Phân nhóm

Ví dụ

distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

[0, 4, 13]

Nguồn

IOI 2021, Ngày 1 — Distributing Candies (candies).