22023번 - Distributing Candies 서브태스크다국어언어 제한함수 구현

문제

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:

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$)

서브태스크

힌트

샘플 그레이더

The sample grader reads in 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ドル \le j \le q - 1$): $l[j]$ $r[j]$ $v[j]$

The sample grader prints your answers in the following format:

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

첨부

• candies.zip