시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 2048 MB85423956.522%

## 문제

Aunty Khong is preparing $n$ boxes of candies for students from a nearby school. The boxes are numbered from $0$ to $n - 1$ and are initially empty. Box $i$ ($0 \le i \le n - 1$) has a capacity of $c[i]$ candies.

Aunty Khong spends $q$ days preparing the boxes. On day $j$ ($0 \le j \le q - 1$), she performs an action specified by three integers $l[j]$, $r[j]$ and $v[j]$ where $0 \le l[j] \le r[j] \le n - 1$ and $v[j] \ne 0$. For each box $k$ satisfying $l[j] \le k \le r[j]$:

• If $v[j] > 0$, Aunty Khong adds candies to box $k$, one by one, until she has added exactly $v[j]$ candies or the box becomes full. In other words, if the box had $p$ candies before the action, it will have $\min{(c[k], p + v[j])}$ candies after the action.
• If $v[j] < 0$, Aunty Khong removes candies from box $k$, one by one, until she has removed exactly $-v[j]$ candies or the box becomes empty. In other words, if the box had $p$ candies before the action, it will have $\max{(0, p + v[j])}$ candies after the action.

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

## 구현

You should implement the following procedure:

int[] distribute_candies(int[] c, int[] l, int[] r, int[] v)
• $c$: an array of length $n$. For $0 \le i \le n - 1$, $c[i]$ denotes the capacity of box $i$.
• $l$, $r$ and $v$: three arrays of length $q$. On day $j$, for $0 \le j \le q - 1$, Aunty Khong performs an action specified by integers $l[j]$, $r[j]$ and $v[j]$, as described above.
• This procedure should return an array of length $n$. Denote the array by $s$. For $0 \le i \le n - 1$, $s[i]$ should be the number of candies in box $i$ after the $q$ days.

## 예제

Consider the following call:

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

This means that box $0$ has a capacity of $10$ candies, box $1$ has a capacity of $15$ candies, and box $2$ has a capacity of $13$ candies.

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, box $1$ has $\max{(0, 15 + v[1])} = 4$ candies. Since $2 > r[1]$, there is no change in the number of candies in box $2$. The number of candies at the end of each day are summarized below:

Day Box $0$ Box $1$ Box $2$
$0$ $10$ $15$ $13$
$1$ $0$ $4$ $13$

As such, the procedure should return $[0, 4, 13]$.

## 제한

• $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] \ne 0$ (for all $0 \le j \le q - 1$)

## 서브태스크

번호 배점 제한
1 3

$n, q \le 2000$

2 8

$v[j] > 0$ (for all $0 \le j \le q - 1$)

3 27

$c[0] = c[1] = \cdots = c[n − 1]$

4 29

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

5 33

## 샘플 그레이더

• line $1$: $n$
• line $2$: $c[0]$ $c[1]$ $\cdots$ $c[n - 1]$
• line $3$: $q$
• line $4 + j$ ($0 \le j \le q - 1$): $l[j]$ $r[j]$ $v[j]$

• line 1: $s[0]$ $s[1]$ $\cdots$ $s[n - 1]$

## 출처

• 문제를 만든 사람: Nguyen Vu Hoang Vuong

## 제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

## 채점 및 기타 정보

• 예제는 채점하지 않는다.