레이팅 미적용JOI 学園にはN 人の生徒がおり,それぞれ1 からN までの番号が付けられている.
JOI 学園では,近日プレゼント交換会が開催される予定である.各生徒はそこに持参するためのプレゼン
トを1 つずつ用意しており,生徒i (1 ≦i ≦N) が持参する予定のプレゼントの価値はAi である.生徒たち
は自分が持参したプレゼントに比べて価値が低すぎるプレゼントを貰うことを嫌がっており,具体的には,
生徒i は価値Bi 未満のプレゼントを受け取ると不満を抱く.ここで,Bi < Ai が成り立っている.
ただし,N 人の生徒全員がプレゼント交換会に実際に参加するとは限らない.JOI 学園のトップである
K 理事長は,プレゼント交換会に参加する生徒のグループとしてQ 個の可能性を検討しており,j 個目
(1 ≦j ≦Q) のグループはRj −Lj + 1 人の生徒Lj, L j + 1, . . . , Rj からなる.
ある2 人以上の生徒のグループについて,誰かが自分の持参したプレゼントを受け取ったり不満を抱いた
りすることなくグループ内でプレゼントを交換できるとき,そのグループはプレゼント交換可能であると
いう.厳密には,m 人(m ≧2) の生徒p1, p2, . . . , pm からなるグループがプレゼント交換可能であるとは,
p1, p2, . . . , pm を並び替えてできる数列q1, q2, . . . , qm であって,以下の条件を共に満たすものが存在するこ
とをいう.なお,qk (1 ≦k ≦m) は生徒pk にプレゼントを渡す生徒の番号を表している.
• すべてのk (1 ≦k ≦m) について,pk , qk.
• すべてのk (1 ≦k ≦m) について,Aqk ≧Bpk.
プレゼント交換会を成功させたいK 理事長は,Q 個のグループそれぞれについてプレゼント交換可能で
あるかどうかを調べようとしている.
生徒の情報とグループの情報が与えられたとき,それぞれのグループについてプレゼント交換可能である
かどうかを判定するプログラムを作成せよ.
第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)
• 2 ≦N ≦500 000.
• 1 ≦Bi < Ai ≦2N (1 ≦i ≦N).
• A1, B1, A2, B2, . . . , AN, BN はすべて異なる.
• 1 ≦Q ≦200 000.
• 1 ≦L j < R j ≦N (1 ≦j ≦Q).
• 入力される値はすべて整数である.
第23 回日本情報オリンピック(JOI 2023/2024) 本選
2024 年2 月4 日(オンライン開催)
- (4 点) N ≦10,Q ≦10.
- (5 点) N ≦18,Q ≦10.
- (10 点) N ≦100 000,A1 ≧2N −2,B1 = 1,Q = 1,L1 = 1,R1 = N.
- (31 点) N ≦100 000,Q ≦10.
- (8 点) N ≦100 000,Ai < Ai+1,Bi < Bi+1 (1 ≦i ≦N −1).
- (12 点) N ≦100 000,Ai < Ai+1 (1 ≦i ≦N −1).
- (18 点) N ≦100 000.
- (12 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N
A1 A2 · · · AN
B1 B2 · · · BN
Q
L1 R1
L2 R2
...
LQ RQ
標準出力にQ 行で出力せよ.j 行目(1 ≦j ≦Q) には,j 個目のグループがプレゼント交換可能であるな
らばYes を,そうでないならばNo を出力せよ.
4
3 8 5 7
2 6 1 4
3
3 4
1 3
1 4
Yes
No
Yes
3
5 6 3
1 4 2
1
1 3
Yes
5
3 4 6 9 10
1 2 5 7 8
3
1 5
1 2
2 4
No
Yes
No
10
2 5 8 10 12 14 16 17 19 20
1 4 7 6 11 13 9 3 18 15
8
2 9
1 6
2 8
2 4
1 2
1 6
7 10
5 8
No
No
Yes
No
No
No
Yes
Yes