問題一覧 > 通常問題

No.1055 牛歩

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 11
作問者 : QCFiumQCFium / テスター : 夕叢霧香(ゆうむらきりか)夕叢霧香(ゆうむらきりか)
3 ProblemId : 3417 / 出題時の順位表
問題文最終更新日: 2020-05-15 23:31:13

問題文

$N$個のマスが左右に一直線に並んでいます。
$M$個の駒が置かれており、$i(1 \le i \le M)$個目の駒は左から$A_i$個目のマスに置かれています。
どの2つの駒も同じマスに置かれていることはありません。
これから$Q$個の指示が順に飛んできます。
$i(1 \le i \le Q)$個目の指示は「$B_i$個目の駒を左又は右の隣り合うマスに動かせ」というものです。
このとき、$N$個のマスの外に出たり同じマスに複数の駒が置かれたりしてはなりません。
全ての指示に従うことはできるでしょうか ?

入力

$N\ M$
$A_1\ A_2\ A_3\ \dots\ A_M$
$Q$
$B_1\ B_2\ B_3\ \dots\ B_Q$

$1 \le N \le 10 ^ 6$
$1 \le M \le \min(N, 2 \times 10 ^ 5)$
$1 \le Q \le 2 \times 10 ^ 5$
$1 \le A_1 \lt A_2 \lt A_3 \lt \dots \lt A_M \le N$
$1 \le B_i \le M(1 \le i \le Q)$
入力は全て整数

出力

可能な場合YESを、不可能な場合NOを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
5 3
1 3 5
3
1 2 1
出力
YES

例えば3回のクエリで順に右右左というように動かすと可能です。

サンプル2
入力
5 3
1 3 5
3
1 3 2
出力
NO

3回目のクエリで詰みます。

サンプル3
入力
3 3
1 2 3
1
2
出力
NO

サンプル4
入力
9 5
1 2 3 8 9
8
3 3 2 2 1 4 5 4
出力
YES

サンプル5
入力
9 5
1 2 3 8 9
9
3 3 3 2 2 1 4 5 4
出力
NO

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