← 返回题目列表

Codeforces · 2065/C1

C1. Skibidus 和 Fanum 税(简单版)

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

这是问题的简单版本。在此版本中,$$$m = 1$$$。

Skibidus获得了两个数组$$$a$$$和$$$b$$$,分别包含$$$n$$$和$$$m$$$元素。对于从$$$1$$$到$$$n$$$的每个整数$$$i$$$,他最多允许执行一次操作:

- 选择一个整数 $$$j$$$,使得 $$$1 \leq j \leq m$$$。设置 $$$a_i := b_j - a_i$$$。请注意,此操作的结果是 $$$a_i$$$ 可能会变为非正数。

Skibidus 需要您帮助确定他是否可以通过执行上述操作多次来按非降序对 $$$a$$$ 进行排序$$$^{\text{*}}$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$\textbf{m = 1}$$$)。

每个测试用例的以下行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。

每个测试用例的以下行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$)。

保证所有测试用例的 $$$n$$$ 之和与 $$$m$$$ 之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以按非降序对 $$$a$$$ 进行排序,则在新行上打印“YES”。否则,在新行上打印“NO”。

任何情况下都可以输出答案。例如,字符串“yEs”、“yes”和“Yes”也将被识别为肯定响应。

示例

输入 #1

5
1 1
5
9
3 1
1 4 3
3
4 1
1 4 2 5
6
4 1
5 4 10 5
4
3 1
9 8 7
8

输出 #1

YES
NO
YES
NO
YES

注意

在第一个测试用例中,$$$[5]$$$ 已经排序。

在第二个测试用例中,可以证明这是不可能的。

在第三个测试用例中,我们可以设置$$$a_3:=b_1-a_3=6-2=4$$$。序列 $$$[1,4,4,5]$$$ 是非降序的。

在最后一种情况下,我们可以对每个索引应用操作。序列变为 $$$[-1,0,1]$$$,按非降序排列。