#P7665. [IOI2021] 分糖果

[IOI2021] 分糖果

题目背景

滥用本题评测将被封号

由于技术限制,请不要使用 C++ 14 (GCC 9) 提交本题。

这是一道交互题,你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件,也不需要实现 main 函数。

题目描述

Khong 阿姨正在给附近⼀所学校的学⽣准备 nn 盒糖果。盒⼦的编号分别为 00n1n - 1,开始时盒⼦都为空。第 ii 个盒⼦ (0in1)(0 \leq i \leq n - 1) ⾄多可以容纳 c[i]c[i] 块糖果(容量为 c[i]c[i])。

Khong 阿姨花了 qq 天时间准备糖果盒。在第 jj(0jq1)(0 \leq j \leq q - 1),她根据三个整数 l[j]l[j]r[j]r[j]v[j]v[j] 执⾏操作,其中 0l[j]r[j]n10 \leq l[j] \leq r[j] \leq n - 1v[j]0v[j] \neq 0。对于每个编号满⾜ l[j]kr[j]l[j] \leq k \leq r[j] 的盒⼦ kk

  • 如果 v[j]>0v[j] > 0,Khong 阿姨将糖果⼀块接⼀块地放⼊第 kk 个盒⼦,直到她正好放了 v[j]v[j] 块糖果或者该盒⼦已满。也就是说,如果该盒⼦在这次操作之前已有 pp 块糖果,那么在这次操作之后盒⼦将有 min(c[k],p+v[j])\min(c[k], p + v[j]) 块糖果。

  • 如果 v[j]<0v[j] < 0,Khong 阿姨将糖果⼀块接⼀块地从第 kk 个盒⼦取出,直到她正好从盒⼦中取出 v[j]-v[j] 块糖果或者该盒⼦已空。也就是说,如果该盒⼦在这次操作之前已有 pp 块糖果,那么在这次操作之后盒⼦将有 max(0,p+v[j])\max(0, p + v[j]) 块糖果。

你的任务是求出 qq 天之后每个盒⼦中糖果的数量。

输入格式

实现细节

你要实现以下函数:

std::vector<int> distribute_candies(
  	std::vector<int> c, std::vector<int> l, 
  	std::vector<int> r, std::vector<int> v)
  • cc:⼀个⻓度为 nn 的数组。 对于 0in10 \leq i \leq n - 1, c[i]c[i] 表⽰盒⼦ ii 的容量。

  • llrrvv:三个⻓度为 qq 的数组。 在第 jj 天, 对于 0jq10 \leq j \leq q - 1,Khong 阿姨执⾏由整数 l[j]l[j]r[j]r[j]v[j]v[j] 决定的操作,如题⾯所述。

输出格式

  • 该函数应该返回⼀个⻓度为 nn 的数组。⽤ ss 表⽰这个数组。 对于 0in10 \leq i \leq n - 1s[i]s[i] 应为 qq 天以后盒⼦ ii 中的糖果数量。
3
10 15 13
2
0 2 20
0 1 -11

0 4 13

提示

例 1

考虑如下调⽤: distribute_candies([10, 15, 13], [0, 0], [2, 1], [20, -11])

这表⽰盒⼦ 00 的容量为 1010 块糖果,盒⼦ 11 的容量为 1515 块糖果,盒⼦ 22 的容量为 1313 块糖果。

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

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

盒子 00 盒子 11 盒子 22
00 1010 1515 1313
11 00 44

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

约束条件

  • 1n2000001 \le n \le 200 000

  • 1q2000001 \le q \le 200 000

  • 1c[i]1091 \le c[i] \le 10 ^ 9 (对所有 0in10 \le i \le n - 1

  • 0l[j]r[j]n10 \le l[j] \le r[j] \le n - 1(对所有 0jq10 \le j \le q - 1

  • 109v[j]109−10 ^ 9 \le v[j] \le 10 ^ 9 , v[j]0v[j] ≠ 0(对所有 0jq10 \le j \le q - 1

子任务

  1. 33 分) n,q2000n, q \leq 2000
  2. 88 分) v[j]>0v[j] > 0(对所有 0jq10 \le j \le q - 1
  3. 2727 分) c[0]=c[1]==c[n1]c[0] = c[1] = \cdots = c[n - 1]
  4. 2929 分) l[j]=0l[j] = 0r[j]=n1r[j] = n - 1(对所有 0jq10 \leq j \leq q - 1
  5. 3333 分) 没有额外的约束条件。

评测程序⽰例

评测程序⽰例读⼊如下格式的输⼊:

  • 11 ⾏: nn
  • 22 ⾏: c[0] c[1]  c[n1]c[0] ~ c[1] ~ \cdots ~ c[n - 1]
  • 33 ⾏: qq
  • 4+j4 + j ⾏ ( 0jq10 \leq j \leq q - 1): l[j] r[j] v[j]l[j] ~ r[j] ~ v[j]

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

11 ⾏: s[0] s[1]  s[n1]s[0] ~ s[1] ~ \cdots ~ s[n - 1]