ダンジョンのデッドロック 2 Elixir(Beta)編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
(電脳言語のオルダーソンループで出題された問題のヒント問題です。8 言語での解答コードと解説が用意されています。)
この問題は前問 (ダンジョンのデッドロック 1) と同じ内容ですが、制約だけが大きくなっています。
あなたは RPG のダンジョンの設計をしています。
そのダンジョンには N 個の部屋が用意されており、それぞれの部屋は 1, 2, ..., N で表されます。このダンジョンでは 1 部屋に 1 プレイヤーしか滞在できません。
また、プレイヤーは M 人いて、現在 i (1 ≦ i ≦ M) 番目のプレイヤーは部屋 S_i (1 ≦ S_i ≦ N) に滞在しています。
ダンジョンをクリアするには、プレイヤーはそれぞれ、部屋を移動する必要があります。
しかし、部屋を移動しようと思ってもその部屋はまだ別のプレイヤーが滞在しているかもしれません。その場合はプレイヤーは部屋を移動することができません。
そこで、それぞれのプレイヤーが部屋を移動できるか事前に判定することにしました。
あなたの仕事は、各 i (1 ≦ i ≦ Q) について、現在の状況から E_i 番目のプレイヤーが部屋 T_i に移動できるか判定することです。
ただし、滞在している部屋と移動先の部屋が同じ場合、つまり S_i = T_i (1 ≦ i ≦ M) の場合、そのプレイヤーは移動ができることとします。また各 i (1 ≦ i ≦ Q) について、部屋を移動できると判定された場合でも、実際に移動はしないものとします。
- 入力される値
-
N M Q
S_1
S_2
...
S_M
E_1 T_1
E_2 T_2
...
E_Q T_Q
・1 行目には、ダンジョンの部屋の数 N ,プレイヤー数 M, 判定する回数 Q がこの順で半角スペース区切りで与えられます。
・続く M 行のうちの i 行目 (1 ≦ i ≦ M) には、i 人目のプレイヤーの現在滞在している部屋 S_i が与えられます。
・続く Q 行のうちの i 行目 (1 ≦ i ≦ Q) には、部屋の移動をするプレイヤーの番号 E_i, 移動先の部屋 T_i がこの順で半角スペース区切りで与えられます。
・入力は合計で M + Q + 1 行となり、 入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
・合計 Q 行出力してください。各行の末尾に改行を入れ、余計な文字、空行を含んではいけません。
・i 行目 (1 ≦ i ≦ Q) には、現在の状況から E_i 番目のプレイヤーが部屋 T_i に移動することができる場合は "Yes" を、できない場合は "No" を出力してください。
- 条件
-
全てのテストケースにおいて、以下の条件を満たします。
・1 ≦ N ≦ 100,000
・1 ≦ M ≦ N
・1 ≦ Q ≦ 100,000
・1 ≦ S_i ≦ N (1 ≦ i ≦ M)
・1 ≦ E_i ≦ M (1 ≦ i ≦ Q)
・1 ≦ T_i ≦ N (1 ≦ i ≦ Q)
・S_i ≠ S_j (1 ≦ i, j ≦ M, i ≠ j)
- 入力例1
-
3 2 3
1
2
1 3
2 3
1 2
- 出力例1
-
Yes
Yes
No
- 入力例2
-
15 10 10
1
2
3
4
5
11
12
13
14
15
1 6
5 6
6 6
8 6
5 11
6 11
9 11
10 11
6 2
8 3
- 出力例2
-
Yes
Yes
Yes
Yes
No
Yes
No
No
No
No
