No.2402 Dirty Stairs and Shoes
タグ : / 解いたユーザー数 188
作問者 : 👑
amentorimaru
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もしくは右上の雲マークをクリックしてアカウントを作成してください。