分数: 266 分
问题陈述
Takahashi 管理购物中心的点卡系统。商场有 N 会员,以及会员 i (1 \leq i \leq N) 的初始积分余额为 S_i.
从现在开始, M 点调整操作将从 1-st 到 M-th。在 j第次操作 (1 \leq j \leq M),值 V_j 已添加至会员当前积分余额 T_j,新的积分余额设置为结果中的最大值, 0。也就是说,如果会员 T_j操作前的积分余额为 P,则操作后的积分余额变为 \max(P + V_j,\ 0)。每个操作在下一个操作开始之前完成。请注意,同一成员可能会受到多次操作。
积分余额没有上限。另一方面,根据上述规则,每次操作后的积分余额始终为 0 或更大。
按顺序执行所有积分调整操作后,确定各会员的积分余额。
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq T_j \leq N (1 \leq j \leq M)
- -10^9 \leq V_j \leq 10^9 (1 \leq j \leq M)
- 所有输入值均为整数。
- 保证所有要输出的值最多为 2^{63}-1 (它们适合签名的 64位整数)。
输入
N M S_1 S_2 \cdots S_N T_1 V_1 T_2 V_2 \vdots T_M V_M
- 第一行包含一个整数 N 代表会员数量和一个整数 M 代表点调整操作的数量,以空格分隔。
- 第二行包含整数 S_1, S_2, \ldots, S_N 代表每个会员的初始积分余额,以空格分隔。
- S_i 代表会员初始积分余额 i.
- 如下 M 行, j第行 (1 \leq j \leq M) 包含一个整数 T_j 代表目标会员号码 j第一个运算和一个整数 V_j 表示要添加的点数,以空格分隔。
输出
执行所有积分调整操作后,按会员顺序打印各会员的积分余额 1, 成员 2, \ldots, 成员 N,用空格分隔,在一行上。最后输出换行符。
样本输入 1
3 4 100 200 300 1 50 2 -150 3 -400 1 -200
示例输出 1
0 50 0
示例输入 2
5 6 0 500 1000 750 300 3 -500 1 100 2 -600 4 250 5 -300 2 200
示例输出 2
100 200 500 1000 0
示例输入 3
10 12 1000000000 0 500000000 999999999 123456789 0 777777777 100000000 999999999 1 1 -1000000000 2 1000000000 3 -500000001 4 1 5 -123456790 6 0 7 -777777777 8 900000000 9 -1000000000 10 999999999 10 -500000000 3 1000000000
示例输出 3
0 1000000000 1000000000 1000000000 0 0 0 1000000000 0 500000000