問題一覧 > 通常問題

No.3369 Find MyakuMyaku

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 16
作問者 : comavius / テスター : Naru820 jupiter_68 rhoo noya2
お気に入りにしたユーザー ProblemId : 12084 / 自分の提出
問題文最終更新日: 2025-11-17 20:50:48
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 作問ハッカソンコンテスト 003 Day2 (順位表) の他の問題:

Story

Let's find MyakuMyaku! Its face parts have turned into rectangles, though...

Problem Statement

There is a $10^9 \times 10^9$ grid. The top-left cell of this grid is called cell $(0,0)$.

For integers $r,c$ between $0$ and $10^9 - 1$, inclusive, the cell reached by moving $r$ cells down and $c$ cells to the right from cell $(0,0)$ is called cell $(r,c)$.

You are given $N$ rectangles $R_1, R_2, \dots , R_N$. $R_i$ is the rectangle whose top-left corner is cell $(h_{i1}, w_{i1}) $ and whose bottom-right corner is cell $(h_{i2},w_{i2})$.

Here, for $i=1,2,\dots,N$, it is guaranteed that $1 \le h_{i1} \le h_{i2} \le H,1 \le w_{i1} \le w_{i2} \le W$ holds.

Solve the following problem for $k = 1,2,...,N$.

Paint the cells contained in at least one of the rectangles $R_1, R_2, \dots , R_k$ black, and paint the cells contained in none of them white.

Determine whether there exist $2$ white cells that are not connected.

Here, $2$ white cells are said to be connected if the $2$ white cells $(i_1, j_1),(i_2,j_2)$ satisfy the following condition.

  • There exists a sequence of cells $(x_1, y_1), (x_2, y_2), \dots, (x_L, y_L)$ satisfying the following conditions.
    • For all $l = 1, 2, \dots, L$, $(x_l, y_l)$ is painted white.
    • For all $l = 1, 2, \dots, L-1$, $|x_l - x_{l+1}| + |y_l - y_{l+1}| = 1$ holds.
    • $(x_1, y_1) = (i_1, j_1)$
    • $(x_L, y_L) = (i_2, j_2)$

Constraints

  • $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$
  • All input values are integers.

Input

$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}$

Output

Output $N$ lines. On the $i$-th line, output the answer for the case $k = i$: Yes if there exist $2$ white cells that are not connected, and No otherwise.

Sample

Sample 1
Input
4 4 4
1 4 1 1
1 1 1 4
1 4 4 4
4 4 1 4
Output
No
No
No
Yes

When $k = 1$, the black cells are the $4$ cells $(1,1),(2,1),(3,1),(4,1)$.

In this case, it can be proved that all white cells are connected to each other, so output No.

When $k = 2$, the black cells are the $7$ cells $(1,1),(1,2),(1,3),(1,4),(2,1),(3,1),(4,1)$.

In this case, it can be proved that all white cells are connected to each other, so output No.

When $k = 3$, the black cells are the $10$ cells $(1,1),(1,2),(1,3),(1,4),(2,1),(2,4),(3,1),(3,4),(4,1),(4,4)$.

In this case, it can be proved that all white cells are connected to each other, so output No.

When $k = 4$, the black cells are the $12$ cells $(1,1),(1,2),(1,3),(1,4),(2,1),(2,4),(3,1),(3,4),(4,1),(4,2),(4,3),(4,4)$.

In this case, it can be proved that cell $(0,0)$ and cell $(2,2)$ are not connected. Therefore, output Yes.

Note that you must output Yes when there exist $2$ white cells that are not connected.

Sample 2
Input
4 3 3
1 1 2 2
2 2 1 1
3 3 2 2
2 2 3 3
Output
No
No
No
Yes

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