← 返回题目列表

AtCoder · abc382_f

I. 掉落的酒吧

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

分数: 525 点

问题陈述

有一个网格 H 行和 W 列。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。

有 N 水平条编号为 1 to N 放置在网格上。 酒吧 i 包括 L_i 大小块 1 \times 1 水平连接,其最左边的块最初位于单元格 (R_i, C_i)。 也就是说,最初,酒吧 i 占据单元格 (R_i, C_i), (R_i, C_i + 1), \dots, (R_i, C_i + L_i - 1)。 确保没有单元格被两个不同的条占用。

当前时间是 t = 0。 每时每刻 t = 0.5 + n 对于一些非负整数 n,以下内容按顺序发生 i = 1, 2, \dots, N:

  • 如果栏 i 不在底行( H-th row),并且 bar 占据的单元格正下方没有任何单元格 i 被任意栏占用,则栏 i 向下移动一个单元格。也就是说,如果那个时候吧 i 占据单元格 (r,C_i),(r,C_i+1),\dots,(r,C_i+L_i-1)\ (r < H),以及单元格 (r + 1, C_i + j) 没有被任何栏占用 j (0 \leq j \leq L_i - 1),然后栏 i 现在占据 (r + 1, C_i), (r + 1, C_i + 1), \dots, (r + 1, C_i + L_i - 1).
  • 否则,什么也不会发生。

让 (R'_i, C_i), (R'_i, C_i + 1), \dots, (R'_i, C_i + L_i - 1) 是 bar 占据的单元格 i 时间 t = 10^{100}。查找 R'_1, R'_2, \dots, R'_N.

约束

  • 1 \leq H, W \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq R_i \leq H
  • 1 \leq C_i \leq W
  • 1 \leq L_i \leq W - C_i + 1
  • 在初始状态下,没有两个不同的条占据单元格。
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

H W N
R_1 C_1 L_1
R_2 C_2 L_2
\vdots
R_N C_N L_N

输出

打印 N 行。 的 i- 第行 (1 \leq i \leq N)应包含 R'_i.


示例输入 1

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

示例输出 1

2
4
3
4

下面三张图代表了有时的网格 t = 0, 1,和 2 从左到右。 彩色矩形代表条形,每个矩形内的数字表示其条形编号。

电网状态变化解释如下:

  • At t = 0.5:
    • i = 1:栏正下方的单元格 1 是 (2,2),(2,3),(2,4)。其中, (2,2) 被栏占用 3 和 (2,4) 被栏占用 4,所以什么也没有发生。
    • i = 2:栏正下方的单元格 2 是 (4,2),(4,3),没有被任何其他栏占用,所以栏 2 向下移动一个单元格。
    • i = 3:栏正下方的单元格 3 是 (3,1),(3,2),没有被任何其他栏占用,所以栏 3 向下移动一个单元格。
    • i = 4:栏正下方的单元格 4 is (3,4),没有被任何其他栏占用,所以栏 4 向下移动一个单元格。
  • At t = 1.5:
    • i = 1:栏正下方的单元格 1 是 (2,2),(2,3),(2,4),没有被任何其他栏占用,所以栏 1 向下移动一个单元格。
    • i = 2:酒吧 2 位于底行,因此没有任何反应。
    • i = 3:栏正下方的单元格 3 是 (4,1),(4,2)。其中, (4,2) 被栏占用 2,所以什么也没有发生。
    • i = 4:栏正下方的单元格 4 is (4,4),没有被任何其他栏占用,所以栏 4 向下移动一个单元格。

有时 t = 2.5, 3.5, \dots,不存在任何栏,其正下方的单元格都未被占用,因此什么也没有发生。因此,此时的网格 t = 10^{100} 与相同 t = 2 (上图最右)。

因此, R'_1 = 2, R'_2 = 4, R'_3 = 3, R'_4 = 4.


示例输入 2

382 382 3
3 3 3
8 8 8
2 2 2

示例输出 2

382
382
381

示例输入 3

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

示例输出 3

5
5
5
4
3
5
4
2