← 返回题目列表

AtCoder · awc0072_c

C. 电池剩余电量

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

分数: 366 分

问题陈述

高桥管理 N 智能手机。智能手机的编号从 1 to N,以及智能手机的初始电池电量 i (1 \leq i \leq N) is S_i.

这些智能手机通过接收应用通知来消耗电池。有一天, Q 通知事件按顺序发生 1-st 到 Q-th。在 j-th (1 \leq j \leq Q) 通知事件,每台编号介于 L_j 和 R_j 包容性减少 1。然而,电池电量为 0 仍为 0。也就是说,如果通知事件所针对的智能手机的电池电量是 b,那么 b 更改为 \max(b - 1,\ 0).

在所有通知事件完成后查找每部智能手机的最终电池电量。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
  • 所有输入均为整数

输入

N Q
S_1 S_2 \ldots S_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 第一行包含一个整数 N 代表智能手机的数量和一个整数 Q 表示通知事件的数量,以空格分隔。
  • 第二行包含整数 S_1, S_2, \ldots, S_N 代表每部智能手机的初始电池电量,以空格分隔。
  • 在下面 Q 行, j第行 (1 \leq j \leq Q) 包含整数 L_j 和 R_j 代表目标智能手机号码的范围 j-第一个通知事件,以空格分隔。

输出

在所有通知事件完成后,按智能手机的顺序打印所有智能手机的电池电量 1 to N,用空格分隔,在一行上。在末尾添加换行符。


示例输入 1

5 3
10 5 3 8 2
1 3
2 4
3 5

示例输出 1

9 3 0 6 1

示例输入 2

4 5
3 1 4 2
1 2
1 2
2 3
3 4
1 4

示例输出 2

0 0 1 0

示例输入 3

10 8
100 0 5 20 3 15 8 0 12 7
1 5
3 7
2 6
5 10
1 10
6 8
4 4
1 3

示例输出 3

97 0 0 15 0 10 4 0 10 5