

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 450 点
問題文
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
出力
色 i で塗られたマスが存在するような整数 i の個数を K として、K + 1 行出力せよ。
1 行目には K の値を出力せよ。
2 行目以降には色 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 で塗られたマスは 5 つ、色 2 で塗られたマスは 4 つ、色 5 で塗られたマスは 3 つです。
入力例 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
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