問題一覧 > 通常問題

No.2402 Dirty Stairs and Shoes

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 188
作問者 : 👑 獅子座じゃない人 / テスター : 👑 amentorimaru
お気に入りにしたユーザー ProblemId : 9817 / 自分の提出
問題文最終更新日: 2023-08-06 14:38:46
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 400 (順位表) の他の問題:

Problem Statement

There is a staircase with $N$ steps. Luella is initially on step $0$ and wants to climb up to step $N$.

$M_1$ of the steps on this staircase are dirty. Step $A_i$ $(1\leq i\leq M_1)$ is dirty, and if Luella lands on it, her shoes become dirty.

Also, $M_2$ of the steps on this staircase have a shoe-wiping mat placed on them. The shoe-wiping mats are placed on step $B_i$ $(1\leq i\leq M_2)$, and if Luella lands on one, her shoes become clean regardless of how many times she has landed on dirty steps.

No step is both dirty and has a shoe-wiping mat. Also, steps $0$ and $N$ are not dirty and do not have a shoe-wiping mat.

When climbing the stairs, Luella can choose either to climb $1$ step or to climb $K$ steps at once without landing on any step in between. However, she cannot climb in a way that goes beyond step $N$.

Step $N$ of the staircase is a sacred place, so she must not land on it with dirty shoes.

When she is initially on step $0$, the shoes Luella is wearing are clean.

Print Yes if she can land on step $N$ with clean shoes by choosing how to climb appropriately, and No otherwise.

Input

$N\ K$
$M_1$
$A_1\ A_2\ A_3\ \ldots\ A_{M_1}$
$M_2$
$B_1\ B_2\ B_3\ \ldots\ B_{M_2}$

  • All inputs are integers.
  • $1\leq N\leq 2\times 10^5$
  • $1\leq K\leq N$
  • $0\leq M_1\lt N$
  • $0\leq M_2\lt N$
  • $0\leq M_1+M_2\lt N$
  • $1\leq A_i\lt N\ (1\leq i\leq M_1)$
  • $1\leq B_i\lt N\ (1\leq i\leq M_2)$
  • $A_i\neq A_j\ (i\neq j)$
  • $B_i\neq B_j\ (i\neq j)$
  • $\{A_i\}\cap\{B_i\}=\varnothing$

Output

Print Yes or No, followed by a newline.

Sample

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

For example, suppose she first climbs to step $1$, then climbs to step $3$ at once. At this point, Luella's shoes become dirty, but if she climbs to step $4$, her shoes become clean. If she then climbs from step $4$ to step $6$ at once, she can land on step $N$ with clean shoes.

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

She cannot climb in a way that goes beyond step $N$.

Sample 3
Input
10 3
6
2 3 5 6 8 9
0

Output
Yes

There are also cases where $M_1=0$ or $M_2=0$.

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