問題一覧 > 通常問題

No.1490 スライムと爆弾

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 59
作問者 : netyo715netyo715 / テスター : 37zigen37zigen
1 ProblemId : 4552 / 出題時の順位表
問題文最終更新日: 2021-04-23 19:50:52

問題文

$H$ 行 $W$ 列のマス目があります。上から $h$ 行目、左から $w$ 列目のマスをマス $(h, w)$ と表します。

マス目上には、$N$ 体のスライムと $M$ 個の爆弾が配置されています。

スライム $i$ は、$T_i \leq h \leq U_i$ と $L_i \leq w \leq R_i$ を満たすマス $(h, w)$ 全てと重なるような形をしています。
スライム $i$ の体力は $A_i$ です。

爆弾 $j$ はマス $(X_j, Y_j)$ に配置されています。
爆弾 $j$ が爆発すると、$X_j-B_j \leq h \leq X_j+B_j$ と $Y_j-B_j \leq w \leq Y_j+B_j$ を満たすマス $(h, w)$ 全てに爆風が届きます。

スライム $i$ と爆弾 $j$ の爆風が重なるとき、スライム $i$ の体力が、爆風と重なったマス1マスにつき $C_j$ 減ります。スライムは体力が0以下になると消滅します。

全ての爆弾が爆発した後で消滅していないスライムの数を出力してください。

入力

$H\ W\ N\ M$
$T_1\ U_1\ L_1\ R_1\ A_1$
$\dots$
$T_N\ U_N\ L_N\ R_N\ A_N$
$X_1\ Y_1\ B_1\ C_1$
$\dots$
$X_M\ Y_M\ B_M\ C_M$
  • 入力される数値は全て整数
  • $1 \leq H \leq 2000$
  • $1 \leq W \leq 2000$
  • $1 \leq N < 10^5$
  • $1 \leq M < 10^5$
  • $1 \leq T_i \leq U_i \leq H$
  • $1 \leq L_i \leq R_i \leq W$
  • $1 \leq A_i \leq 10^9$
  • $1 \leq X_i \leq H$
  • $1 \leq Y_i \leq W$
  • $0 \leq B_i < 2000$
  • $1 \leq C_i \leq 10^6$

出力

全ての爆弾が爆発した後で消滅していないスライムの数を出力してください。
最後に改行してください。

サンプル

サンプル1
入力
5 6 3 1
1 2 1 3 5
1 2 6 6 1
4 5 4 5 4
3 3 1 3
出力
2

スライムの配置と爆風の範囲は以下の図の通りです。

スライム1と爆風の重なっているマスは2マスあり、スライム1の体力が6減ります。体力が0以下になりスライム1は消滅します。

スライム2と爆風は1マスも重なっておらず、ダメージを受けません。よって、スライム2は消滅しません。

スライム3と爆風が重なっているマスは1マスあり、スライム3の体力が3減ります。しかし、体力は1残るのでスライム3は消滅しません。

スライム2とスライム3が消滅せずに残るので、答えは2です。

サンプル2
入力
2 2 1 1
1 1 1 1 1
2 2 0 1000000
出力
1
サンプル3
入力
100 100 10 5
77 97 23 43 351
9 64 68 100 5984
17 60 4 95 9884
100 100 67 77 3382
88 95 86 97 4328
25 28 89 95 6202
47 94 24 84 3844
70 83 78 90 3852
17 37 59 61 5910
24 29 96 100 6769
30 9 968 1
84 95 381 1
2 19 205 1
93 27 935 1
2 2 720 1
出力
6

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。