← 返回题目列表

AtCoder · abc346_e

H. 油漆

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

分数: 450 点

问题陈述

有一个网格 H 行和 W 列。最初,所有单元格都涂上颜色 0.

您将按顺序执行以下操作 i = 1, 2, \ldots, M.

  • If T_i = 1,重新绘制所有单元格 A_i-th 行 有颜色 X_i.

  • If T_i = 2,重新绘制所有单元格 A_i-th 栏目 有颜色 X_i.

所有操作完成后,对于每种颜色 网格上存在的 i ,找到涂有颜色的单元格数量 i.

约束

  • 1 \leq H, W, M \leq 2 \times 10^5
  • T_i \in \lbrace 1, 2 \rbrace
  • 1 \leq A_i \leq H 对于每个 i 这样 T_i = 1,
  • 1 \leq A_i \leq W 对于每个 i 这样 T_i = 2.
  • 0 \leq X_i \leq 2 \times 10^5
  • 所有输入值均为整数。

输入

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

H W M
T_1 A_1 X_1
T_2 A_2 X_2
\vdots
T_M A_M X_M

输出

让 K 是不同整数的数量 i 这样就有涂有颜色的单元格 i。打印 K + 1 行。

第一行应包含以下值 K.

对于每种颜色,第二行和后续行应包含 网格上存在的 i ,颜色编号 i 以及涂有该颜色的单元格数量。

具体来说, (i + 1)第行 (1 \leq i \leq K) 应包含颜色编号 c_i 和单元格数量 x_i 涂上颜色 c_i,按此顺序,用空格分隔。

在这里,打印颜色编号 按升序排列。也就是说,确保 c_1 < c_2 < \ldots < c_K。另请注意 x_i > 0 为必填项。


示例输入 1

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

示例输出 1

3
0 5
2 4
5 3

这些操作将更改网格中单元格的颜色,如下所示:

0000   0000   0000   0000   0000
0000 → 5555 → 5550 → 5550 → 5550 
0000   0000   0000   3333   2222

最终,有五个单元格被涂上颜色 0,四色同色 2,以及三个带颜色的 5.


示例输入 2

1 1 5
1 1 1
1 1 10
2 1 100
1 1 1000
2 1 10000

示例输出 2

1
10000 1

示例输入 3

5 5 10
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
2 1 6
2 2 7
2 3 8
2 4 9
2 5 10

示例输出 3

5
6 5
7 5
8 5
9 5
10 5