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