Skip to content
Sign in

マスキングテープ (Masking Tape)

Unrated
日本語

Language

Contribute a translation
Time limit
2000 ms
Memory limit
1024 MB
Submissions
0
Correct
0
Solved by
0
AC rate
—

Statement

JOI 君は，紙とマスキングテープを使い，色塗りをして遊んでいる．

紙は長方形であり，縦 \(H\) 行，横 \(W\) 列のマス目が描かれている．上から \(i\) 行目 (\(1 \leqq i \leqq H\))，左から \(j\) 列目 (\(1 \leqq j \leqq W\)) のマスをマス \((i, j)\) と呼ぶ．

それぞれのマスには色が \(1\) つ定められている．色は整数で表され，はじめすべてのマスの色は \(0\) である．

JOI 君は，この紙とマスキングテープを用いて \(Q\) 回の操作を行う． \(k\) 回目 (\(1 \leqq k \leqq Q\)) の操作は，整数 \(q_k\) の値に応じて以下のように説明される．

  • \(q_k = 1\) のとき，この操作は整数 \(x_k, y_k, c_k\) で表される．マス \((x_k, y_k)\), \((x_k + 1, y_k)\), \((x_k, y_k + 1)\), \((x_k + 1, y_k + 1)\) それぞれについて，マスがマスキングテープで覆われていなければ，そのマスの色を \(c_k\) に変更する．マスがマスキングテープで覆われているならば，そのマスには何もしない．
  • \(q_k = 2\) のとき，この操作は整数 \(x_k, y_k\) で表される．マス \((x_k, y_k)\), \((x_k + 1, y_k)\), \((x_k, y_k + 1)\), \((x_k + 1, y_k + 1)\) をマスキングテープで覆う．

\(Q\) 回の操作が終わった後，すべてのマスキングテープを剥がす．なお，あるマスのマスキングテープを剥がしたとき，そのマスの色はマスキングテープで覆われる直前の色と同じになる．

\(Q\) 回の操作の情報が与えられたとき，最終的な紙のすべてのマスの色を求めるプログラムを作成せよ．

Constraints

  • \(2 \leqq H \leqq 500\)．
  • \(2 \leqq W \leqq 500\)．
  • \(1 \leqq Q \leqq 200 \: 000\)．
  • \(q_k\) は \(1\) か \(2\) のいずれかである (\(1 \leqq k \leqq Q\))．
  • \(q_k = 1\) のとき，\(1 \leqq x_k \leqq H - 1\)，\(1 \leqq y_k \leqq W - 1\)，\(1 \leqq c_k \leqq 10^9\) (\(1 \leqq k \leqq Q\))．
  • \(q_k = 2\) のとき，\(1 \leqq x_k \leqq H - 1\)，\(1 \leqq y_k \leqq W - 1\) (\(1 \leqq k \leqq Q\))．
  • 入力される値はすべて整数である．

Subtasks

  1. (\(32\) 点) \(H = 2\)，\(W = 2\)，\(q_k = 1\) (\(1 \leqq k \leqq Q\))．
  2. (\(32\) 点) \(q_k = 1\) (\(1 \leqq k \leqq Q\))．
  3. (\(36\) 点) 追加の制約はない．

Input

入力は以下の形式で与えられる．

\(H\) \(W\) \(Q\)
(\(Query \: 1\))
(\(Query \: 2\))
\(\vdots\)
(\(Query \: Q\))

各 (\(Query \: k\)) (\(1 \leqq k \leqq Q\)) にはいくつかの整数が空白区切りで書かれている．そのうち \(1\) 個目の整数が \(q_k\) であり，この行の内容は以下のいずれかである．

  • \(q_k = 1\) のとき，この行には続いて \(3\) 個の整数 \(x_k, y_k, c_k\) が空白区切りで書かれている．
  • \(q_k = 2\) のとき，この行には続いて \(2\) 個の整数 \(x_k, y_k\) が空白区切りで書かれている．

Output

最終的な紙のすべてのマスの色を \(H\) 行で出力せよ．\(i\) 行目 (\(1 \leqq i \leqq H\)) には，\(W\) 個の整数を空白区切りで出力せよ．ここで，\(j\) 番目 (\(1 \leqq j \leqq W\)) に出力する整数はマス \((i, j)\) の色とする．

Examples

Sample input 1
5 5 4
1 2 2 1
2 1 2
2 3 3
1 1 3 5
Sample output 1
0 0 0 5 0
0 1 1 5 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0

\(4\) 回の操作を順に見ていく．

\(1\) 回目の操作について，\(q_1 = 1\) である．マス \((2, 2)\)，\((2, 3)\)，\((3, 2)\)，\((3, 3)\) はすべてマスキングテープで覆われていないので，色を \(1\) に変更する．

このとき，紙は以下のようになっている．

0  0  0  0  0
0  1  1  0  0
0  1  1  0  0
0  0  0  0  0
0  0  0  0  0

\(2\) 回目の操作について，\(q_2 = 2\) である．マス \((1, 2)\)，\((1, 3)\)，\((2, 2)\)，\((2, 3)\) をマスキングテープで覆う．

このとき，紙は以下のようになっている．なお，マスキングテープで覆ったマスの色を表す整数の右に * を付けた．

0  0* 0* 0  0
0  1* 1* 0  0
0  1  1  0  0
0  0  0  0  0
0  0  0  0  0

\(3\) 回目の操作について，\(q_3 = 2\) である．マス \((3, 3)\)，\((3, 4)\)，\((4, 3)\)，\((4, 4)\) をマスキングテープで覆う．

このとき，紙は以下のようになっている．

0  0* 0* 0  0
0  1* 1* 0  0
0  1  1* 0* 0
0  0  0* 0* 0
0  0  0  0  0

\(4\) 回目の操作について，\(q_4 = 1\) である．マス \((1, 4)\)，\((2, 4)\) はマスキングテープで覆われていないので，色を \(5\) に変更する．マス \((1, 3)\)，\((2, 3)\) はマスキングテープで覆われているので，何もしない．

このとき，紙は以下のようになっている．

0  0* 0* 5  0
0  1* 1* 5  0
0  1  1* 0* 0
0  0  0* 0* 0
0  0  0  0  0

したがって，最終的な紙のすべてのマスの色は出力例のようになっている．

この入出力例は小課題 \(3\) の制約を満たす．

Sample input 2
5 5 3
1 1 1 2
1 3 3 3
1 2 4 2
Sample output 2
2 2 0 0 0
2 2 0 2 2
0 0 3 2 2
0 0 3 3 0
0 0 0 0 0

この入出力例は小課題 \(2, 3\) の制約を満たす．

Sample input 3
10 10 10
2 5 7
2 5 6
1 5 6 1
1 9 2 1
2 1 1
1 2 4 2
2 3 2
1 2 2 3
1 9 9 2
1 8 8 1
Sample output 3
0 0 0 0 0 0 0 0 0 0
0 0 3 2 2 0 0 0 0 0
0 0 0 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0
0 1 1 0 0 0 0 1 1 2
0 1 1 0 0 0 0 0 2 2

この入出力例は小課題 \(3\) の制約を満たす．

Notes

JOI 2025 · JCIOI · CC BY-SA 4.0

Tags

No tags yet

Source