Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
ストーリー
いろはちゃんを捕まえていた、ひときわ巨大な異形。僕は、そいつと一対一で向かい合う。
「同胞を屠ってきたのは貴様らか。できることなら我が直々に手を下してしまいたいものだが、これ以上手駒を失うのは痛い。」 「そこで一つ、貴様と我でゲームをしようではないか。」
問題文
あなたと怪物で次のゲームをします。
- はじめ、いくつかの長方形がある。どの長方形の縦あるいは横の長さも整数である。
- あなたから交互に長方形を1つ選んで、自分が切ることのできる方向で等分する。このとき、切ってできる長方形の縦あるいは横の長さも整数でなければならない。数式で表現すると、大きさが h_i \times w_i の長方形があるとき、 n | h_i なる整数 n(>1) について、大きさが h_i / n \times w_i の長方形を n 枚つくるか、 n | w_i なる整数 n(>1) について、大きさが h_i \times w_i / n の長方形を n 枚つくる。
先に行動ができなくなった方が負けです。
切ることができる方向について、あなたはすべての長方形について横方向に切ることができ、いくつかの長方形について縦にも切ることができます。
対して、相手はすべての長方形について縦方向に切ることができ、いくつかの長方形について横にも切ることができます。
それぞれの長方形および切ることができる向きは、あわせて 4 つの数字 a,b,h,w\ (a,b\in\{0,1\},h,w は正の整数) で表されます。
長方形は縦の長さが h で、横の長さが w です。
a = 1 のとき、かつそのときに限りあなたはこの長方形を縦にも切ることができます。
b = 1 のとき、かつそのときに限り相手はこの長方形を横にも切ることができます。
N 個の長方形と切る向きの情報が与えられるので、次の Q 個の質問に答えてください。
- i 番目の質問では、 1 \leq l_i \leq r_i \leq N なる整数 l_i, r_i が与えられる。 l_i 番目の長方形から r_i 番目の長方形までを使ってゲームをするとき、どちらが勝つか判定してください。
制約
- 1 \leq N \leq 10^5
- 0 < h_i \leq 10^5, 0 < w_i \leq 10^5 (i=1,2,\dots,N)
- a_i,b_i \in \{0,1\} (i=1,2,\dots,N)
- 1 \leq Q \leq 10^5
- 1 \leq l_i \leq r_i \leq N (i=1,2,\dots,Q)
部分点
この問題には部分点が設定されている。
- どちらのプレイヤーも縦横どちらにも切ることができるような入力に正解すると、400 点が得られる。
入力
入力は以下の形式で標準入力から与えられます。
N a_1 b_1 h_1 w_1 : a_N b_N h_N w_N Q l_1 r_1 : l_Q r_Q
出力
Q 個それぞれの質問について、あなたが勝つなら Yes
、相手が勝つなら No
と Q 行にわたって出力してください。
入力例 1
1 1 1 3 4 1 1 1
出力例 1
Yes
例えばはじめに長方形を縦に 2 等分すると、相手と対称な手を打つことで勝つことができます。 このケースは部分点に含まれます。
入力例 2
2 1 0 2 5 0 1 5 2 1 1 2
出力例 2
No
相手にものまね戦略を取られてしまうと負けてしまいます。 このケースは部分点に含まれません。
入力例 3
13 1 1 3 1 1 1 4 1 1 1 5 9 1 1 2 6 1 1 5 3 1 1 5 8 1 1 9 7 1 1 9 3 1 1 2 3 1 1 8 4 1 1 6 2 1 1 6 4 1 1 3 3 10 3 13 1 6 1 5 9 10 6 11 1 12 3 9 2 4 4 11 1 3
出力例 3
No Yes Yes Yes Yes No Yes No Yes Yes
このケースは部分点に含まれます。
入力例 4
20 0 1 121 219 1 0 300 241 1 1 215 112 0 1 268 156 0 1 33 204 1 0 202 111 1 1 59 70 1 1 272 83 0 0 190 285 1 1 291 283 1 1 299 90 1 1 80 48 0 1 107 291 0 1 158 136 1 1 127 223 1 1 227 93 1 1 79 183 1 0 92 26 1 0 190 300 0 1 294 38 30 14 20 14 19 11 19 11 15 4 8 9 10 5 12 1 7 18 19 12 14 13 15 6 19 6 10 2 5 9 18 9 13 18 19 17 18 4 13 16 18 2 13 13 13 7 12 1 8 2 20 4 12 7 7 10 17 14 18 5 12
出力例 4
Yes Yes Yes No No Yes Yes Yes Yes No No Yes Yes Yes No No Yes Yes No Yes Yes No Yes Yes Yes No Yes No No Yes
このケースは部分点に含まれません。