難易度評価

難易度を1〜10段階で評価できます。投票はあとから変更・取り消しできます。

難易度(投票) Lv.5.0 (2票)

投票の分布
  1. Lv.10票
  2. Lv.20票
  3. Lv.30票
  4. Lv.40票
  5. Lv.52票
  6. Lv.60票
  7. Lv.70票
  8. Lv.80票
  9. Lv.90票
  10. Lv.100票

難易度の目安を見る ↗

ログインして難易度を投票

外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

Snow and Rain

作成者 yura1685

難易度(作成者設定) Lv.5

難易度(投票) Lv.5.0 (2票)

実行時間制限
2 秒
メモリ制限
512 MiB

問題文

縦 HH 行、横 WW 列のマス目で表される山があります。上から ii 行目、左から jj 列目のマスを (i,j)(i, j) と書き、マス (i,j)(i, j) の標高は Ai,jA_{i,j} です。はじめ、どのマスにも雪は積もっていません。 これから QQ 日分の天気が順に与えられます。kk 日目の天気は次のいずれかです。

  • タイプ1(雪):1 r1 c1 r2 c2 S の形式で与えられる。r1≤i≤r2r_1 \le i \le r_2 かつ c1≤j≤c2c_1 \le j \le c_2 を満たすすべてのマス (i,j)(i, j) の積雪が SS 増える。
  • タイプ2(雨):2 r c の形式で与えられる。マス (r,c)(r, c) に大量の雨が降る。雨は、上下左右に隣接するマスのうち標高が今いるマス以下のマスへ流れることを繰り返す。マス (r,c)(r, c) 自身と、雨が流れ着くことのできるすべてのマスの積雪が 00 になる。

QQ 日分の天気がすべて終わったあと、各マスに積もっている雪の量を求めてください。

制約

  • 1≤H,W≤10001 \le H, W \le 1000
  • 1≤Q≤2×1051 \le Q \le 2 \times 10^5
  • 0≤Ai,j≤1090 \le A_{i,j} \le 10^9
  • 雪の天気について、1≤r1≤r2≤H,1≤c1≤c2≤W,1≤S≤1091\le r_1\le r_2\le H, 1\le c_1\le c_2\le W,1\le S\le10^9
  • 雨の天気について、1≤r≤H,1≤c≤W1\le r\le H,1\le c\le W
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

HH WW QQ A1,1A_{1,1} A1,2A_{1,2} …\ldots A1,WA_{1,W} ⋮\vdots AH,1A_{H,1} AH,2A_{H,2} …\ldots AH,WA_{H,W} Query1\mathrm{Query}_1 ⋮\vdots QueryQ\mathrm{Query}_Q

QuerykQuery_k はkk 日目の天気を表し、次のいずれかの形式です。

11 r1r_1 c1c_1 r2r_2 c2c_2 SS
22 rr cc

出力

HH 行出力してください。ii 行目には、最終的にマス (i,1),(i,2),…,(i,W)(i, 1), (i, 2), \ldots, (i, W) に積もっている雪の量を空白区切りで出力してください。


サンプル 1

入力

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

出力

0 0 0 0
3 5 5 0
3 8 8 0
  • 11 日目:すべてのマスに 33 の雪が積もります。
  • 22 日目:マス (1,1)(1, 1) に雨が降ります。この雨は (1,2)→(1,3)→(1,4)→(2,4)→(3,4)(1, 2) → (1, 3) → (1, 4) → (2, 4) → (3, 4) と流れ、(1,2)(1, 2) から (2,2)(2, 2)、(1,3)(1, 3) から (2,3)(2, 3) にも流れます。
  • 33 日目:(2,2),(2,3),(3,2),(3,3)(2, 2),(2, 3),(3, 2),(3, 3) に 55 の雪が積もり、それぞれの積雪量は 5,5,8,85, 5, 8, 8 になります。
  • 44 日目:マス (2,4)(2, 4) に雨が降ります。隣のうち標高 1 以下なのは (3,4)(3, 4) だけで、この 22 マスはもともと積雪 00 です。

サンプル 2

入力

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

出力

6 6 2 2
6 0 0 2
2 0 1 3
2 2 3 3

サンプル 3

入力

2 5 4
1 2 3 4 5
5 4 3 2 1
1 1 1 2 5 10
2 1 3
2 2 3
1 1 5 2 5 7

出力

0 0 0 10 17
10 10 0 0 7