← 返回题目列表

AtCoder · iroha2019_day4_j

J. 我不会再放弃了

中文机器翻译题面 查看原题

配点 : 1200 点

故事

一个特别大的异常物体正在控制着小彩羽。我将一对一地面对他。

“屠杀我同胞的就是你们吗?如果可以的话,我想直接对你们下手,但再失去棋子就很痛苦了。” “那你和我玩个游戏怎么样?”

問題文

你和怪物将玩以下游戏。

  • 首先,有一些矩形。任何矩形的长度或宽度都是整数。
  • 轮流选择一个矩形,并在您可以切割的任何方向上将其分成相等的部分。此时,切出的矩形的长度或宽度也必须是整数。用数学表达,大小为 当你有一个 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

此案例不计入部分积分。


解説

解説