← 返回题目列表

AtCoder · joi2021ho_b

B. 雪球

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

配点: 100 点

JOI平原是一个非常大的平原,东西向延伸。这个平原可以被认为是一条数轴,每个点都用以东为正的坐标表示。 JOI 平原是冬天 N 雪球是在不同的坐标处创建的。从西方到雪球 它们的编号最大为 1 从 N 。第一,滚雪球 i (1 \leqq i \leqq N) 坐标是整数 这是 X_i 。

JOI 平原也因冬季强风而闻名。你是 Q 我们获得了每日风力观测数据。j 日目 (1 \leqq j \leqq Q) 风数据是一个整数 它由 W_j 表示。 当W_j 为负数时,向西, 当W_j 不为负时,方向为东,强度为 意味着 \lvert W_j \rvert 的风吹起来了。

当风吹时,雪球会沿着与风相同的方向滚动,滚动的距离等于风的强度。即 j 日目 (1 \leqq j \leqq Q) 在坐标的开头 当 x 处有雪球时,雪球有坐标 坐标来自 x 滚动到 x + W_j 。j 最终,雪球的坐标是 它变成 x + W_j 。然而,每天所有的雪球都在同一时间以相同的速度滚动。

一开始,整个JOI平原都被雪覆盖了。当雪球在积雪的区域滚动时,雪会粘附在雪球上,增加雪球的重量,该区域的雪就会消失。也就是说, 设a为整数且坐标 假设雪保持在 a 滚动到 a + 1 范围内。此时,如果雪球在这个范围内滚动,则雪球的重量将为 1 增加,坐标 a 滚动到 a + 1 范围内的积雪已经消失。然而,即使雪球滚到没有雪的地方,雪球的重量也保持不变。

最初,所有雪球的重量为 这是 0 。另外,观察到的 Q 白天没有下新雪。

你 Q 我想知道一天结束时雪球的重量。

雪球的初始坐标,Q 给定每日风力观测数据,Q 编写一个程序来计算一天结束时每个雪球的重量。


入力

输入是按以下格式从标准输入给出的。所有输入值都是整数。

N Q
X_1 \cdots X_N
W_1
\vdots
W_Q

出力

到标准输出 N 行。i 行目 (1 \leqq i \leqq N)是 Q 一天结束时滚雪球 打印 i 的重量。


制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq Q \leqq 200\,000.
  • \lvert X_i \rvert \leqq 1\,000\,000\,000\,000 \ (= 10^{12}) (1 \leqq i \leqq N).
  • X_i < X_{i + 1} (1 \leqq i \leqq N - 1).
  • \lvert W_j \rvert \leqq 1\,000\,000\,000\,000 \ (= 10^{12}) (1 \leqq j \leqq Q).

小課題

  1. (33 点) N \leqq 2\,000,Q \leqq 2\,000.
  2. (67 点)没有额外的限制。

入力例 1

4 3
-2 3 5 8
2
-4
7

出力例 1

5
4
2
6

在此输入示例中,雪球的坐标和重量变化如下。

  • 最初,每个雪球的坐标是 从 1 开始 -2, 3, 5, 8 。每个雪球的重量是 1 开始 0, 0, 0, 0 。
  • 1 当天力量向东 2 风在吹。1 一天结束时,每个雪球的坐标是 1 开始 0, 5, 7, 10 。每个雪球的重量是 1 开始 2, 2, 2, 2 。
  • 2 当天力量向西 4 风在吹。2 一天结束时,每个雪球的坐标是 1 开始 -4, 1, 3, 6 。每个雪球的重量是 1 开始 4, 4, 2, 3 。
  • 3 当天力量向东 7 风在吹。3 一天结束时,每个雪球的坐标是 1 开始 3, 8, 10, 13 。每个雪球的重量是 1 开始 5, 4, 2, 6 。

因此3 一天结束时每个雪球的重量 按顺序输出 5, 4, 2, 6 。


入力例 2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

出力例 2

3000000000000

入力例 3

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

出力例 3

14
8
7
9
11
10
9
8
5
10