← 返回题目列表

AtCoder · joi2016ho_e

E. 地质断层

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

配点: 100 点

在遥远的过去,一种名为IOI文明的高级文明蓬勃发展。然而,这个先进的文明最终因火山爆发而灭亡。 IOI文明沿着笔直的河流繁盛,当IOI文明消亡时,地表平坦。 IOI文明废墟在坐标平面上。 x 可以将其视为一个轴。y 轴表示高度方向。也就是说,在坐标平面中,直线 y = 0 代表地球表面,面积 y > 0 覆盖地面和区域 y < 0 代表地下。还有,当IOI文明灭亡时,a 年前 (a \geqq 0) 是一条直线。 它位于 y = -a 。

IOI文明毁灭后,在IOI文明遗址, Q 发生了地壳运动。i 回目 (1 \leqq i \leqq Q处的地壳变形为 X_i,方向 D_i,变化量 它由 L_i 表示。D_i 是 由于它被视为 1 或 2 。 它仅由i 第二次地壳变形发生如下。

  • 地层移动如下。 当
    • D_i = 1 时,故障是一个点 倾斜穿过 (X_i, 0) 斜坡经过 1 沿直线建造,且该直线上方区域的地层高度沿直线增加。 移动 L_i 。即这条线上方的点 (x, y) 是一个点 移至 (x + L_i, y + L_i) 。
    • D_i = 2 时,故障是一个点 倾斜穿过 (X_i, 0) 斜坡经过 -1 沿直线建造,且该直线上方区域的地层高度沿直线增加。 移动 L_i 。即这条线上方的点 (x, y) 是一个点 移至 (x - L_i, y + L_i) 。
  • 紧接着,该区域 所有 y > 0 地层因风化而消失。

时代变了,考古学家JOI博士决定挖掘IOI文明的遗迹。 JOI博士想知道地球表面的地质地层在哪里,以及IOI文明在多少年前消失了。我们知道发生了什么样的构造运动。你的工作是取代JOI博士。 每个满足1 \leqq i \leqq N 的整数 对于 i ,点 (i - 1, 0) 和点 (i, 0)目的是查出IOI文明在多少年前被毁灭。

課題

IOI 鉴于文明所在地发生的事情的信息,所有整数 i (1 \leqq i \leqq N),这一点 输出IOI文明灭绝前多少年,地球表面的地层 (i - 1, 0) 和点 (i, 0) 之间。


入力

从标准输入读取以下输入。 在

  • 1 行中,2 整数 N, Q 以空格作为分隔符。这意味着寻求答案的点数是 N,地壳运动次数为 Q 。
  • 继续 来自行 Q 行 i 行目 (1 \leqq i \leqq Q)有3 整数 X_i, D_i, L_i 以空格作为分隔符。这是i 第二次地壳形变的位置是 X_i,方向是 D_i,变化量为 L_i 。

出力

输出是 由 N 行组成。标准输出 i 行目 (1 \leqq i \leqq N)有一点 输出一个整数,表示 (i - 1, 0) 和点 (i, 0) 之间地球表面的地层距离IOI文明灭绝还有多少年。


制限

所有输入数据满足以下条件。

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq Q \leqq 200\,000.
  • -1\,000\,000\,000 \leqq X_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q).
  • 1 \leqq D_i \leqq 2 (1 \leqq i \leqq Q).
  • 1 \leqq L_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq Q).

小課題

小課題 1 [18 点]

满足以下条件。

  • N \leqq 100.
  • Q \leqq 100.
  • -100 \leqq X_i \leqq 100 (1 \leqq i \leqq Q).
  • L_i = 1 (1 \leqq i \leqq Q).

小課題 2 [16 点]

满足以下条件。

  • N \leqq 3,000.
  • Q \leqq 3,000.

小課題 3 [66 点]

没有其他限制。


入力例 1

10 2
12 1 3
2 2 2

出力例 1

3
3
5
5
5
5
5
5
2
2

该输入示例对应于下图。


入力例 2

10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1

出力例 2

5
5
4
5
5
5
5
5
4
4

这个输入示例是 1 满足约束。


入力例 3

15 10
28 1 7
-24 2 1
1 1 1
8 1 1
6 2 1
20 1 3
12 2 2
-10 1 3
7 2 1
5 1 2

出力例 3

15
14
14
14
14
12
12
12
12
12
12
12
15
15
12