시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 2048 MB 33 14 14 63.636%

문제

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

No additional constraints.

샘플 그레이더

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

첨부

출처

Olympiad > International Olympiad in Informatics > IOI 2021 > Day 1 1번

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

제출할 수 있는 언어

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

채점 및 기타 정보

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