Background

Due to technical limitations, please do not use C++ 14 (GCC 9) to submit this problem.

This is an interactive problem. You only need to implement the function required in the code.

Your code does not need to include any extra header files, and you do not need to implement the main function.

Problem Description

Aunt Khong is preparing $n$ boxes of candies for students at a nearby school. The boxes are numbered from $0$ to $n - 1$, and initially all boxes are empty. Box $i$ $(0 \leq i \leq n - 1)$ can hold at most $c[i]$ candies (its capacity is $c[i]$).

Aunt Khong spends $q$ days preparing the candy boxes. On day $j$ $(0 \leq j \leq q - 1)$, she performs an operation based on three integers $l[j]$, $r[j]$, and $v[j]$, where $0 \leq l[j] \leq r[j] \leq n - 1$ and $v[j] \neq 0$. For every box $k$ such that $l[j] \leq k \leq r[j]$:

• If $v[j] > 0$, Aunt Khong puts candies into box $k$ one by one until she has put exactly $v[j]$ candies or the box becomes full. That is, if the box contains $p$ candies before this operation, then after this operation it will contain $\min(c[k], p + v[j])$ candies.

• If $v[j] < 0$, Aunt Khong takes candies out of box $k$ one by one until she has taken out exactly $-v[j]$ candies or the box becomes empty. That is, if the box contains $p$ candies before this operation, then after this operation it will contain $\max(0, p + v[j])$ candies.

Your task is to compute the number of candies in each box after $q$ days.

Input Format

Implementation details

You need to implement the following function:

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

• $c$: an array of length $n$. For $0 \leq i \leq n - 1$, $c[i]$ is the capacity of box $i$.

• $l$, $r$, and $v$: three arrays of length $q$. On day $j$, for $0 \leq j \leq q - 1$, Aunt Khong performs the operation determined by integers $l[j]$, $r[j]$, and $v[j]$, as described in the statement.

Output Format

• The function should return an array of length $n$. Let this array be $s$. For $0 \leq i \leq n - 1$, $s[i]$ should be the number of candies in box $i$ after $q$ days.

3
10 15 13
2
0 2 20
0 1 -11

0 4 13

Hint

Example 1

Consider the following call: distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

This means box $0$ has capacity $10$, box $1$ has capacity $15$, and box $2$ has capacity $13$.

At the end of day $0$, box $0$ has $\min(c[0], 0 + v[0]) = 10$ candies, box $1$ has $\min(c[1], 0 + v[0]) = 15$ candies, and box $2$ has $\min(c[2], 0 + v[0]) = 13$ candies.

At the end of day $1$, box $0$ has $\max(0, 10 + v[1]) = 0$ candies, and box $1$ has $\max(0, 15 + v[1]) = 4$ candies. Since $2 > r[1]$, the number of candies in box $2$ does not change. The summary at the end of each day is as follows:

In this case, the function should return $[0, 4, 13]$.

Constraints

• $1 \le n \le 200 000$

• $1 \le q \le 200 000$

• $1 \le c[i] \le 10 ^ 9$ （for all $0 \le i \le n - 1$）

• $0 \le l[j] \le r[j] \le n - 1$ (for all $0 \le j \le q - 1$)

• $−10 ^ 9 \le v[j] \le 10 ^ 9$, $v[j] \neq 0$ (for all $0 \le j \le q - 1$)

Subtasks

1. ($3$ points) $n, q \leq 2000$.
2. ($8$ points) $v[j] > 0$ (for all $0 \leq j \leq q - 1$).
3. ($27$ points) $c[0] = c[1] = \cdots = c[n - 1]$.
4. ($29$ points) $l[j] = 0$ and $r[j] = n - 1$ (for all $0 \leq j \leq q - 1$).
5. ($33$ points) No additional constraints.

Sample grader

The sample grader reads the input in the following format:

• Line $1$: $n$.
• Line $2$: $c[0] ~ c[1] ~ \cdots ~ c[n - 1]$.
• Line $3$: $q$.
• Line $4 + j$ ($0 \leq j \leq q - 1$): $l[j] ~ r[j] ~ v[j]$.

The sample grader prints your answer in the following format:

• Line $1$: $s[0] ~ s[1] ~ \cdots ~ s[n - 1]$.

Translated by ChatGPT 5