TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P8329
  • 题目
  • P8329[IOI2021] 分糖果(candies)
    限制 : 时间限制 : - MS   空间限制 : 1048576 KB
    评测说明 : 4s,1GB
    问题描述

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

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

    • 如果 \(v[i]>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\) 天之后每个盒子中糖果的数量。

    输入格式

    已将原题的输入方式从交互式改为传统方式

    第一行一个数 \(n\)
    第二行 \(n\) 个数 \(c[0],\cdots,c[n-1]\)
    第三行一个数 \(q\) 。 接下来 \(q\) 行,每行三个数 \(l[j],r[j],v[j]\)

    输出格式

    输出一行 \(n\) 个数,第 \(i(0\leq i\leq n-1)\) 个数是 \(q\) 天后盒子 \(i\) 的糖果数量。

    样例输入

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

    样例输出

    0 4 13

    提示

    样例1解释

    盒子 \(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\leq n\leq 200\;000\)
    \(1\leq q\leq 200\;000\)
    \(1\leq c[i]\leq 10^9\)
    \(0\leq l[j]\leq r[j]\leq n-1\)
    \(-10^9\leq v[j] \leq 10^9\)\(v[j]\neq 0\)

    子任务 \(1(3\%)\)\(n,q\leq 2\;000\)
    子任务 \(2(8\%)\)\(v[j]>0\)
    子任务 \(3(27\%)\)\(c[0]=c[1]=\dots=c[n-1]\)
    子任务 \(4(29\%)\)\(l[j]=0\)\(r[j]=n-1\)
    子任务 \(5(33\%)\) : 没有额外的约束条件。