問題一覧 > 通常問題

No.1490 Slimes and Bombs

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 82
作問者 : netyo715 / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 4552 / 自分の提出
問題文最終更新日: 2026-10-19 08:22:55
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 292 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell in the $h$-th row from the top and the $w$-th column from the left is denoted by cell $(h, w)$.

On the grid, there are $N$ slimes and $M$ bombs.

Slime $i$ has a shape that overlaps all cells $(h, w)$ satisfying $T_i \leq h \leq U_i$ and $L_i \leq w \leq R_i$.
The health of slime $i$ is $A_i$.

Bomb $j$ is placed on cell $(X_j, Y_j)$.
When bomb $j$ explodes, the blast reaches all cells $(h, w)$ satisfying $X_j-B_j \leq h \leq X_j+B_j$ and $Y_j-B_j \leq w \leq Y_j+B_j$.

When slime $i$ overlaps the blast of bomb $j$, the health of slime $i$ decreases by $C_j$ for each cell overlapping the blast. A slime disappears when its health becomes 0 or less.

Print the number of slimes that have not disappeared after all the bombs have exploded.

Input

$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$
  • All input values are integers.
  • $1 \leq H \leq 2000$
  • $1 \leq W \leq 2000$
  • $1 \leq N \leq 10^5$
  • $1 \leq M \leq 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$

Output

Print the number of slimes that have not disappeared after all the bombs have exploded.
Print a newline at the end.

Sample

Sample 1
Input
5 6 3 1
1 2 1 3 5
1 2 6 6 1
4 5 4 5 4
3 3 1 3
Output
2

The placement of the slimes and the range of the blast are shown in the figures below.

Slime 1 overlaps the blast in 2 cells, so the health of slime 1 decreases by 6. Its health becomes 0 or less, and slime 1 disappears.

Slime 2 does not overlap the blast in any cell and takes no damage. Therefore, slime 2 does not disappear.

Slime 3 overlaps the blast in 1 cell, so the health of slime 3 decreases by 3. However, 1 health remains, so slime 3 does not disappear.

Slimes 2 and 3 remain without disappearing, so the answer is 2.

Sample 2
Input
2 2 1 1
1 1 1 1 1
2 2 0 1000000
Output
1
Sample 3
Input
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
Output
6

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