No.3369 Find MyakuMyaku
タグ : / 解いたユーザー数 13
作問者 :
comavius
/ テスター :
Naru820
jupiter_68
rhoo
noya2
ストーリー
ミャクミャクを見つけましょう！顔のパーツが長方形になってしまいましたが...
問題文
$10^9 \times 10^9$ のマス目があります。このマス目の一番左上のマスをマス $(0,0)$ と呼びます。
$0$ 以上 $10^9 - 1$ 以下の整数 $r,c$ に対し、マス $(0,0)$ から下に $r$ マス、右に $c$ マス移動した位置にあるマスをマス $(r,c)$ と呼びます。
$N$ 個の長方形 $R_1, R_2, \dots , R_N$ が与えられます。$R_i$ は左上の隅がマス $(h_{i1}, w_{i1}) $ 、右下の隅がマス $(h_{i2},w_{i2})$ であるような長方形です。
ここで、$i=1,2,\dots,N$ について、$1 \le h_{i1} \le h_{i2} \le H,1 \le w_{i1} \le w_{i2} \le W$ が成り立つことが保証されます。
$k = 1,2,...,N$ について以下の問題を解いてください。
長方形 $R_1, R_2, \dots , R_k$ のいずれかに含まれるマスを黒に、いずれにも含まれないマスを白に塗ります。連結でない $2$ つの白いマスが存在するか判定してください。
ただし、$2$ つの白いマスが連結であるとは、$2$ つの白いマス $(i_1, j_1),(i_2,j_2)$ が以下の条件を満たすことをいいます。
- マスの列 $(x_1, y_1), (x_2, y_2), \dots, (x_L, y_L)$ が存在して、以下の条件を満たす。
- すべての $l = 1, 2, \dots, L$ について、$(x_l, y_l)$ は白く塗られている。
- すべての $l = 1, 2, \dots, L-1$ について、$|x_l - x_{l+1}| + |y_l - y_{l+1}| = 1$ が成り立つ。
- $(x_1, y_1) = (i_1, j_1)$
- $(x_L, y_L) = (i_2, j_2)$
制約
- $1\le N, H, W \le 10^3$
- $1 \le h_{i1} \le h_{i2} \le H$
- $1 \le w_{i1} \le w_{i2} \le W$
- 入力は全て整数
入力
$N \space H \space W$
$h_{11} \space h_{12} \space w_{11} \space w_{12}$
$h_{21} \space h_{22} \space w_{21} \space w_{22}$
$\vdots$
$h_{N1} \space h_{N2} \space w_{N1} \space w_{N2}$
出力
$N$ 行出力してください。$i$ 行目には、$k = i$ とした場合の答えを、連結でない $2$ つの白いマスが存在するならば Yes,そうでないならば No として出力してください。
サンプル
サンプル1
入力
4 4 4 1 4 1 1 1 1 1 4 1 4 4 4 4 4 1 4
出力
No No No Yes
$k = 1$ のとき、黒く塗られたマスはマス $(1,1),(2,1),(3,1),(4,1)$ の $4$ 個です。
この時、すべての白いマスどうしが連結であることが証明できるので、Noを出力してください。
$k = 2$ のとき、黒く塗られたマスはマス $(1,1),(1,2),(1,3),(1,4),(2,1),(3,1),(4,1)$ の $7$ 個です。
この時、すべての白いマスどうしが連結であることが証明できるので、Noを出力してください。
$k = 3$ のとき、黒く塗られたマスはマス $(1,1),(1,2),(1,3),(1,4),(2,1),(2,4),(3,1),(3,4),(4,1),(4,4)$ の $10$ 個です。
この時、すべての白いマスどうしが連結であることが証明できるので、Noを出力してください。
$k = 4$ のとき、黒く塗られたマスはマス $(1,1),(1,2),(1,3),(1,4),(2,1),(2,4),(3,1),(3,4),(4,1),(4,2),(4,3),(4,4)$ の $12$ 個です。
この時、マス $(0,0)$ と マス $(2,2)$ が連結でないことが証明できます。よってYesを出力してください。
連結でない $2$ つの白いマスが存在する場合にYesを出力する必要があることに注意してください。
サンプル2
入力
4 3 3 1 1 2 2 2 2 1 1 3 3 2 2 2 2 3 3
出力
No No No Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。