← 返回题目列表

AtCoder · awc0110_a

A. 点卡余额管理

中文机器翻译题面 查看原题

分数: 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