← 返回题目列表

Codeforces · 1786/B

B. 蛋糕装配线

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

面包店的蛋糕流水线再次优化,现在一次可以制作$$$n$$$个蛋糕!在最后一步中,每个 $$$n$$$ 蛋糕都应该涂上巧克力。

考虑传送带上的侧视图,让它成为一条数轴。第 $$$i$$$ 个蛋糕占据了这条线上的线段 $$$[a_i - w, a_i + w]$$$,每对这些线段没有公共点。传送带上方有 $$$n$$$ 分配器,当按下公共按钮时,来自第 $$$i$$$ 个分配器的巧克力将覆盖传送带段 $$$[b_i - h, b_i + h]$$$。每对这些线段也没有共同点。

对应于第一个示例的蛋糕和分配器。

该传送带部件的校准尚未执行,因此您需要进行校准。确定是否可以移动传送带,使每个蛋糕上都有一些巧克力,并且蛋糕外面没有巧克力。您可以假设传送带足够长,因此蛋糕永远不会掉落。另请注意,该按钮只能按一次。

在第一个示例中,我们可以如图所示移动蛋糕。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$w$$$ 和 $$$h$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le w, h \le 10^5$$$; $$$h \le w$$$) — 蛋糕和分配器的数量,以及蛋糕的半角以及分配巧克力的部分。

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 蛋糕中心的位置。对于所有$$$i$$$,保证$$$a_i + w < a_{i + 1} - w$$$。

第三行包含 $$$n$$$ 整数 $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ ($$$1 \le b_i \le 10^9$$$) — 分配器的位置。对于所有$$$i$$$,保证$$$b_i + h < b_{i + 1} - h$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出“是”,如果可以移动传送带,使每个蛋糕最终都有一些巧克力,并且蛋糕外面没有巧克力,否则输出“否”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

4
3 10 5
65 95 165
40 65 145
5 2 1
1 6 11 16 21
4 9 14 19 24
3 3 2
13 22 29
5 16 25
4 4 1
27 36 127 136
35 50 141 144

输出 #1

YES
YES
NO
YES

注意

第一个示例如声明中的附图所示。

在第二个示例中,例如,我们可以移动传送带,使蛋糕的中心位于 $$$4, 9, 14, 19, 24$$$。

在第三个示例中,我们无法相应地移动传送带。