310126: CF1786B. Cake Assembly Line
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Cake Assembly Line
题意翻译
有一个无限长的传送带，传送带上有 $n$ 个蛋糕，天花板上有 $n$ 个喷嘴。一开始每个蛋糕中心的位置是 $a_i$，宽度是 $2w$（也就是这个蛋糕占据的空间是 $[a_i-w,a_i+w]$）；每个喷嘴中心位置是 $b_i$，宽度是 $2h$。 你可以随意移动传动带，但蛋糕间的相对位置不会改变，并且喷嘴的位置也不会发生变化。问能不能通过转动传送带的方式，使得每个喷嘴下面都有一个蛋糕，每个蛋糕上面都有一个喷嘴，并且喷嘴挤出的奶油不会掉到传动带上。 多组数据。题目描述
A cake assembly line in a bakery was once again optimized, and now $ n $ cakes are made at a time! In the last step, each of the $ n $ cakes should be covered with chocolate. Consider a side view on the conveyor belt, let it be a number line. The $ i $ -th cake occupies the segment $ [a_i - w, a_i + w] $ on this line, each pair of these segments does not have common points. Above the conveyor, there are $ n $ dispensers, and when a common button is pressed, chocolate from the $ i $ -th dispenser will cover the conveyor segment $ [b_i - h, b_i + h] $ . Each pair of these segments also does not have common points.  Cakes and dispensers corresponding to the first example.The calibration of this conveyor belt part has not yet been performed, so you are to make it. Determine if it's possible to shift the conveyor so that each cake has some chocolate on it, and there is no chocolate outside the cakes. You can assume that the conveyour is long enough, so the cakes never fall. Also note that the button can only be pressed once.  In the first example we can shift the cakes as shown in the picture.输入输出格式
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^5 $ ). The description of the test cases follows. The first line of each test case contains three integers $ n $ , $ w $ , and $ h $ ( $ 1 \le n \le 10^5 $ ; $ 1 \le w, h \le 10^5 $ ; $ h \le w $ ) — the number of cakes and dispensers, as well as the halfwidths of cakes and segments on which the chocolate is dispensed. The second line contains $ n $ integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the positions of the cakes centers. It is guaranteed that $ a_i + w < a_{i + 1} - w $ for all $ i $ . The third line contains $ n $ integers $ b_1 $ , $ b_2 $ , ..., $ b_n $ ( $ 1 \le b_i \le 10^9 $ ) — the positions of the dispensers. It is guaranteed that $ b_i + h < b_{i + 1} - h $ for all $ i $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .
输出格式
For each test case output "YES", if it's possible to shift the conveyor in such a way that each cake ends up with some chocolate, and no chocolate is outside the cakes, and "NO" otherwise. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
输入输出样例
输入样例 #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说明
The first example is shown in the figures in the statement. In the second example, we can move the conveyor, for example, so that the centers of the cakes are at $ 4, 9, 14, 19, 24 $ . In the third example, we can't move the conveyor accordingly.Input
题意翻译
有一个无限长的传送带，传送带上有 $n$ 个蛋糕，天花板上有 $n$ 个喷嘴。一开始每个蛋糕中心的位置是 $a_i$，宽度是 $2w$（也就是这个蛋糕占据的空间是 $[a_i-w,a_i+w]$）；每个喷嘴中心位置是 $b_i$，宽度是 $2h$。 你可以随意移动传动带，但蛋糕间的相对位置不会改变，并且喷嘴的位置也不会发生变化。问能不能通过转动传送带的方式，使得每个喷嘴下面都有一个蛋糕，每个蛋糕上面都有一个喷嘴，并且喷嘴挤出的奶油不会掉到传动带上。 多组数据。Output
**题意翻译**
有一个无限长的传送带，传送带上有 $ n $ 个蛋糕，天花板上有 $ n $ 个喷嘴。一开始每个蛋糕中心的位置是 $ a_i $，宽度是 $ 2w $（也就是这个蛋糕占据的空间是 $[a_i-w,a_i+w]$）；每个喷嘴中心位置是 $ b_i $，宽度是 $ 2h $。
你可以随意移动传动带，但蛋糕间的相对位置不会改变，并且喷嘴的位置也不会发生变化。问能不能通过转动传送带的方式，使得每个喷嘴下面都有一个蛋糕，每个蛋糕上面都有一个喷嘴，并且喷嘴挤出的奶油不会掉到传动带上。
多组数据。
**题目描述**
一个面包店的蛋糕装配线再次进行了优化，现在一次可以制作 $ 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 $）——蛋糕中心的 positions. 保证对于所有 $ i $ 有 $ a_i + w < a_{i + 1} - w $。
第三行包含 $ n $ 个整数 $ b_1 $，$ b_2 $，...，$ b_n $（$ 1 \le b_i \le 10^9 $）——分配器的 positions. 保证对于所有 $ i $ 有 $ b_i + h < b_{i + 1} - h $。
保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。
**输出格式**
对于每个测试用例输出 "YES"，如果可以通过移动传送带的方式使得每个蛋糕最终都有一些巧克力覆盖，并且没有巧克力掉在蛋糕外面，否则输出 "NO"。
你可以以任何大小写输出答案。例如，字符串 "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
```**题意翻译** 有一个无限长的传送带，传送带上有 $ n $ 个蛋糕，天花板上有 $ n $ 个喷嘴。一开始每个蛋糕中心的位置是 $ a_i $，宽度是 $ 2w $（也就是这个蛋糕占据的空间是 $[a_i-w,a_i+w]$）；每个喷嘴中心位置是 $ b_i $，宽度是 $ 2h $。 你可以随意移动传动带，但蛋糕间的相对位置不会改变，并且喷嘴的位置也不会发生变化。问能不能通过转动传送带的方式，使得每个喷嘴下面都有一个蛋糕，每个蛋糕上面都有一个喷嘴，并且喷嘴挤出的奶油不会掉到传动带上。 多组数据。 **题目描述** 一个面包店的蛋糕装配线再次进行了优化，现在一次可以制作 $ 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 $）——蛋糕中心的 positions. 保证对于所有 $ i $ 有 $ a_i + w < a_{i + 1} - w $。 第三行包含 $ n $ 个整数 $ b_1 $，$ b_2 $，...，$ b_n $（$ 1 \le b_i \le 10^9 $）——分配器的 positions. 保证对于所有 $ i $ 有 $ b_i + h < b_{i + 1} - h $。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式** 对于每个测试用例输出 "YES"，如果可以通过移动传送带的方式使得每个蛋糕最终都有一些巧克力覆盖，并且没有巧克力掉在蛋糕外面，否则输出 "NO"。 你可以以任何大小写输出答案。例如，字符串 "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 ```
有一个无限长的传送带，传送带上有 $ n $ 个蛋糕，天花板上有 $ n $ 个喷嘴。一开始每个蛋糕中心的位置是 $ a_i $，宽度是 $ 2w $（也就是这个蛋糕占据的空间是 $[a_i-w,a_i+w]$）；每个喷嘴中心位置是 $ b_i $，宽度是 $ 2h $。
你可以随意移动传动带，但蛋糕间的相对位置不会改变，并且喷嘴的位置也不会发生变化。问能不能通过转动传送带的方式，使得每个喷嘴下面都有一个蛋糕，每个蛋糕上面都有一个喷嘴，并且喷嘴挤出的奶油不会掉到传动带上。
多组数据。
**题目描述**
一个面包店的蛋糕装配线再次进行了优化，现在一次可以制作 $ 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 $）——蛋糕中心的 positions. 保证对于所有 $ i $ 有 $ a_i + w < a_{i + 1} - w $。
第三行包含 $ n $ 个整数 $ b_1 $，$ b_2 $，...，$ b_n $（$ 1 \le b_i \le 10^9 $）——分配器的 positions. 保证对于所有 $ i $ 有 $ b_i + h < b_{i + 1} - h $。
保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。
**输出格式**
对于每个测试用例输出 "YES"，如果可以通过移动传送带的方式使得每个蛋糕最终都有一些巧克力覆盖，并且没有巧克力掉在蛋糕外面，否则输出 "NO"。
你可以以任何大小写输出答案。例如，字符串 "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
```**题意翻译** 有一个无限长的传送带，传送带上有 $ n $ 个蛋糕，天花板上有 $ n $ 个喷嘴。一开始每个蛋糕中心的位置是 $ a_i $，宽度是 $ 2w $（也就是这个蛋糕占据的空间是 $[a_i-w,a_i+w]$）；每个喷嘴中心位置是 $ b_i $，宽度是 $ 2h $。 你可以随意移动传动带，但蛋糕间的相对位置不会改变，并且喷嘴的位置也不会发生变化。问能不能通过转动传送带的方式，使得每个喷嘴下面都有一个蛋糕，每个蛋糕上面都有一个喷嘴，并且喷嘴挤出的奶油不会掉到传动带上。 多组数据。 **题目描述** 一个面包店的蛋糕装配线再次进行了优化，现在一次可以制作 $ 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 $）——蛋糕中心的 positions. 保证对于所有 $ i $ 有 $ a_i + w < a_{i + 1} - w $。 第三行包含 $ n $ 个整数 $ b_1 $，$ b_2 $，...，$ b_n $（$ 1 \le b_i \le 10^9 $）——分配器的 positions. 保证对于所有 $ i $ 有 $ b_i + h < b_{i + 1} - h $。 保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式** 对于每个测试用例输出 "YES"，如果可以通过移动传送带的方式使得每个蛋糕最终都有一些巧克力覆盖，并且没有巧克力掉在蛋糕外面，否则输出 "NO"。 你可以以任何大小写输出答案。例如，字符串 "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 ```