プレゼント交換 (Gift Exchange)

JOI 学園には \(N\) 人の生徒がおり，それぞれ \(1\) から \(N\) までの番号が付けられている．

JOI 学園では，近日プレゼント交換会が開催される予定である． 各生徒はそこに持参するためのプレゼントを \(1\) つずつ用意しており，生徒 \(i\) (\(1\leqq i \leqq N\)) が持参する予定のプレゼントの価値は \(A_i\) である． 生徒たちは自分が持参したプレゼントに比べて価値が低すぎるプレゼントを貰うことを嫌がっており，具体的には，生徒 \(i\) は価値 \(B_i\) 未満のプレゼントを受け取ると不満を抱く． ここで，\(B_i < A_i\) が成り立っている．

ただし，\(N\) 人の生徒全員がプレゼント交換会に実際に参加するとは限らない． JOI 学園のトップである K 理事長は，プレゼント交換会に参加する生徒のグループとして \(Q\) 個の可能性を検討しており，\(j\) 個目 (\(1\leqq j\leqq Q\)) のグループは \(R_j-L_j+1\) 人の生徒 \(L_j,L_j+1,\dots,R_j\) からなる．

ある \(2\) 人以上の生徒のグループについて，誰かが自分の持参したプレゼントを受け取ったり不満を抱いたりすることなくグループ内でプレゼントを交換できるとき，そのグループはプレゼント交換可能であるという． 厳密には，\(m\) 人 (\(m \geqq 2\)) の生徒 \(p_1,p_2,\dots,p_m\) からなるグループがプレゼント交換可能であるとは，\(p_1,p_2,\dots,p_m\) を並び替えてできる数列 \(q_1,q_2,\dots,q_m\) であって，以下の条件を共に満たすものが存在することをいう． なお，\(q_k\) (\(1\leqq k\leqq m\)) は生徒 \(p_k\) にプレゼントを渡す生徒の番号を表している．

• すべての \(k\) (\(1\leqq k\leqq m\)) について，\(p_k \neq q_k\)．
• すべての \(k\) (\(1\leqq k\leqq m\)) について，\(A_{q_k} \geqq B_{p_k}\)．

プレゼント交換会を成功させたい K 理事長は，\(Q\) 個のグループそれぞれについてプレゼント交換可能であるかどうかを調べようとしている．

生徒の情報とグループの情報が与えられたとき，それぞれのグループについてプレゼント交換可能であるかどうかを判定するプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる．

\(N\)
\(A_1\) \(A_2\) \(\cdots\) \(A_N\)
\(B_1\) \(B_2\) \(\cdots\) \(B_N\)
\(Q\)
\(L_1\) \(R_1\)
\(L_2\) \(R_2\)
\(\vdots\)
\(L_Q\) \(R_Q\)

標準出力に \(Q\) 行で出力せよ． \(j\) 行目 (\(1 \leqq j \leqq Q\)) には，\(j\) 個目のグループがプレゼント交換可能であるならば Yes を，そうでないならば No を出力せよ．

• \(2 \leqq N \leqq 500\,000\)．
• \(1 \leqq B_i < A_i \leqq 2N\) (\(1\leqq i\leqq N\))．
• \(A_1,B_1,A_2,B_2,\dots,A_N,B_N\) はすべて異なる．
• \(1 \leqq Q \leqq 200\,000\)．
• \(1 \leqq L_j < R_j \leqq N\) (\(1\leqq j\leqq Q\))．
• 入力される値はすべて整数である．

1. (\(4\) 点) \(N \leqq 10\)，\(Q \leqq 10\)．
2. (\(5\) 点) \(N \leqq 18\)，\(Q \leqq 10\)．
3. (\(10\) 点) \(N \leqq 100\,000\)，\(A_1 \geqq 2N-2\)，\(B_1=1\)，\(Q=1\)，\(L_1=1\)，\(R_1=N\)．
4. (\(31\) 点) \(N \leqq 100\,000\)，\(Q \leqq 10\)．
5. (\(8\) 点) \(N \leqq 100\,000\)，\(A_i < A_{i+1}\)，\(B_i < B_{i+1}\) (\(1\leqq i\leqq N-1\))．
6. (\(12\) 点) \(N \leqq 100\,000\)，\(A_i < A_{i+1}\) (\(1\leqq i\leqq N-1\))．
7. (\(18\) 点) \(N \leqq 100\,000\)．
8. (\(12\) 点) 追加の制約はない．

JOI 2024 · JCIOI · CC BY-SA 4.0