103464: [Atcoder]ABC346 E - Paint
Description
Score: $450$ points
Problem Statement
There is a grid with $H$ rows and $W$ columns. Initially, all cells are painted with color $0$.
You will perform the following operations in the order $i = 1, 2, \ldots, M$.
-
If $T_i = 1$, repaint all cells in the $A_i$-th row with color $X_i$.
-
If $T_i = 2$, repaint all cells in the $A_i$-th column with color $X_i$.
After all operations are completed, for each color $i$ that exists on the grid, find the number of cells that are painted with color $i$.
Constraints
- $1 \leq H, W, M \leq 2 \times 10^5$
- $T_i \in \lbrace 1, 2 \rbrace$
- $1 \leq A_i \leq H$ for each $i$ such that $T_i = 1$,
- $1 \leq A_i \leq W$ for each $i$ such that $T_i = 2$.
- $0 \leq X_i \leq 2 \times 10^5$
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$H$ $W$ $M$ $T_1$ $A_1$ $X_1$ $T_2$ $A_2$ $X_2$ $\vdots$ $T_M$ $A_M$ $X_M$
Output
Let $K$ be the number of distinct integers $i$ such that there are cells painted with color $i$. Print $K + 1$ lines.
The first line should contain the value of $K$.
The second and subsequent lines should contain, for each color $i$ that exists on the grid, the color number $i$ and the number of cells painted with that color.
Specifically, the $(i + 1)$-th line $(1 \leq i \leq K)$ should contain the color number $c_i$ and the number of cells $x_i$ painted with color $c_i$, in this order, separated by a space.
Here, print the color numbers in ascending order. That is, ensure that $c_1 < c_2 < \ldots < c_K$. Note also that $x_i > 0$ is required.
Sample Input 1
3 4 4 1 2 5 2 4 0 1 3 3 1 3 2
Sample Output 1
3 0 5 2 4 5 3
The operations will change the colors of the cells in the grid as follows:
0000 0000 0000 0000 0000 0000 → 5555 → 5550 → 5550 → 5550 0000 0000 0000 3333 2222
Eventually, there are five cells painted with color $0$, four with color $2$, and three with color $5$.
Sample Input 2
1 1 5 1 1 1 1 1 10 2 1 100 1 1 1000 2 1 10000
Sample Output 2
1 10000 1
Sample Input 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
Sample Output 3
5 6 5 7 5 8 5 9 5 10 5
Input
Output
问题描述
有一个$H$行$W$列的网格。最初,所有的单元格都被涂成颜色$0$。
你将按照顺序执行以下操作:$i = 1, 2, \ldots, M$。
-
如果$T_i = 1$,将第$A_i$行的所有单元格涂成颜色$X_i$。
-
如果$T_i = 2$,将第$A_i$列的所有单元格涂成颜色$X_i$。
完成所有操作后,对于网格中存在的每个颜色$i$,找出涂成颜色$i$的单元格数量。
限制条件
- $1 \leq H, W, M \leq 2 \times 10^5$
- $T_i \in \lbrace 1, 2 \rbrace$
- 对于每个$T_i = 1$的$i$,$1 \leq A_i \leq H$,
- 对于每个$T_i = 2$的$i$,$1 \leq A_i \leq W$。
- $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$和涂成颜色$c_i$的单元格数量$x_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