UOJ Logo Universal Online Judge

UOJ

#660. 【IOI2021】candies

附件下载 统计

由于某些原因本题仅支持 C++, C++11 语言的提交。

Khong 阿姨正在给附近一所学校的学生准备 $n$ 盒糖果。盒子的编号分别为 $0$ 到 $n - 1$,开始时盒子都为空。第 $i$ 个盒子($0 \le i \le n - 1$)至多可以容纳 $c[i]$ 块糖果(容量为 $c[i]$)。

Khong 阿姨花了 $q$ 天时间准备糖果盒。在第 $j$ 天($0 \le j \le q - 1$),她根据三个整数 $l[j]$、$r[j]$ 和 $v[j]$ 执行操作,其中 $0 \le l[j] \le r[j] \le n - 1$ 且 $v[j] \ne 0$。对于每个编号满足 $l[j] \le k \le r[j]$ 的盒子 $k$:

  • 如果 $v[j] > 0$,Khong 阿姨将糖果一块接一块地放入第 $k$ 个盒子,直到她正好放了 $v[j]$ 块糖果或者该盒子已满。也就是说,如果该盒子在这次操作之前已有 $p$ 块糖果,那么在这次操作之后盒子将有 $\min{(c[k], p + v[j])}$ 块糖果。
  • 如果 $v[j] < 0$,Khong 阿姨将糖果一块接一块地从第 k 个盒子取出,直到她正好从盒子中取出 $-v[j]$ 块糖果或者该盒子已空。也就是说,如果该盒⼦在这次操作之前已有 $p$ 块糖果,那么在这次操作之后盒子将有 $\max{(0, p + v[j])}$ 块糖果。

你的任务是求出 $q$ 天之后每个盒子中糖果的数量。

实现细节

你必须引用 candies.h 头文件。

你要实现以下函数:

int[] distribute_candies(int[] c, int[] l, int[] r, int[] v)
  • $c$:一个长度为 $n$ 的数组。对于 $0 \le i \le n - 1$,$c[i]$ 表示盒子 $i$ 的容量。
  • $l$、$r$ 和 $v$:三个长度为 $q$ 的数组。在第 $j$ 天,对于 $0 \le j \le q - 1$,Khong 阿姨执行由整数 $l[j]$、$r[j]$ 和 $v[j]$ 决定的操作,如题面所述。
  • 该函数应该返回一个长度为 $n$ 的数组。用 $s$ 表示这个数组。对于 $0 \le i \le n - 1$,$s[i]$ 应为 $q$ 天以后盒子 $i$ 中的糖果数量。

输入格式

评测程序示例读入如下格式的输入:

  • 第 $1$ 行:$n$
  • 第 $2$ 行:$c[0] \; c[1] \; \ldots \; c[n - 1]$
  • 第 $3$ 行:$q$
  • 第 $4 + j$ 行($0 \le j \le q - 1$):$l[j] \; r[j] \; v[j]$

输出格式

评测程序⽰例按照以下格式打印你的答案:

  • 第 $1$ 行:$s[0] \; s[1] \; \ldots \; s[n - 1]$

样例一

input

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

output

0 4 13

explanation

考虑如下调用:

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

这表示盒子 $0$ 的容量为 $10$ 块糖果,盒子 $1$ 的容量为 $15$ 块糖果,盒子 $2$ 的容量为 $13$ 块糖果。

在第 $0$ 天结束时,盒子 $0$ 有 $\min{(c[0], 0 + v[0])} = 10$ 块糖果,盒子 $1$ 有 $\min{(c[1], 0 + v[0])} = 15$ 块糖果,盒子 $2$ 有 $\min{(c[2], 0 + v[0])} = 13$ 块糖果。

在第 $1$ 天结束时,盒子 $0$ 有 $\max{(0, 10 + v[1])} = 0$ 块糖果,盒子 $1$ 有 $\max(0, 15 + v[1]) = 4$ 块糖果。因为 $2 > r[1]$,盒子 $2$ 中的糖果数量没有变化。每一天结束时糖果的数量总结如下:

盒子 $0$ 盒子 $1$ 盒子 $2$
$0$ $10$ $15$ $13$
$1$ $0$ $4$ $13$

就此情况,函数应该返回 $[0, 4, 13]$。

数据范围

对于所有数据:

  • $1 \le n \le 200 \, 000$
  • $1 \le q \le 200 \, 000$
  • $1 \le c[i] \le {10}^9$(对所有 $0 \le i \le n - 1$)
  • $0 \le l[j] \le r[j] \le n - 1$(对所有 $0 \le j \le q - 1$)
  • $-{10}^9 \le v[j] \le {10}^9$,$v[j] \ne 0$(对所有 $0 \le j \le q - 1$)
子任务 分值 特殊限制
$1$ $3$ $n, q \le 2000$
$2$ $8$ $v[j] > 0$(对所有 $0 \le j \le q - 1$)
$3$ $27$ $c[0] = c[1] = \cdots = c[n - 1]$
$4$ $29$ $l[j] = 0$ 和 $r[j] = n - 1$(对所有 $0 \le j \le q - 1$)
$5$ $33$ 没有额外的约束条件

时间限制:$\texttt{4s}$

空间限制:$\texttt{2GB}$