← 返回题目列表

Codeforces · 1923/B

B. 怪物来袭!

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

您正在玩电脑游戏。该游戏的当前等级可以建模为一条直线。您的角色位于该行的 $$$0$$$ 点。有 $$$n$$$ 怪物试图杀死你的角色;第 $$$i$$$ 个怪物的生命值等于 $$$a_i$$$,并且最初位于 $$$x_i$$$ 点。

每秒都会发生以下情况:

- 首先,你向怪物发射最多 $$$k$$$ 子弹。每颗子弹只瞄准一个怪物,并使其生命值降低 $$$1$$$。对于每颗子弹,您可以任意选择其目标(例如,您可以向一个怪物发射所有子弹,向不同的怪物发射所有子弹,或选择任何其他组合)。任何怪物都可以成为子弹的目标,无论其位置和任何其他因素如何;
- 然后,所有生命值为 $$$0$$$ 或更少的活着的怪物都会死亡;
- 然后,所有活着的怪物都会向你移动$$$1$$$点(你左边的怪物将坐标增加$$$1$$$,你右边的怪物将坐标减少$$$1$$$)。如果任何怪物到达你的角色(移动到$$$0$$$点),你就输了。

你能生存并杀死所有 $$$n$$$ 怪物而不让它们到达你的角色吗?

输入

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

每个测试用例由三行组成:

- 第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5$$$; $$$1 \le k \le 2 \cdot 10^9$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$);
- 第三行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$-n \le x_1 < x_2 < x_3 < \dots < x_n \le n$$$; $$$x_i \ne 0$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,如果您可以在 $$$n$$$ 怪物到达您的角色之前杀死它们,则打印 YES,否则打印 NO。

您可以以任何大小写(大写或小写)输出答案的每个字母。例如,字符串 yEs、yes、Yes 和 YES 都将被识别为肯定响应。

示例

输入 #1

5
3 2
1 2 3
-1 2 3
2 1
1 1
-1 1
4 10
3 4 2 5
-3 -2 1 3
5 3
2 1 3 2 5
-3 -2 3 4 5
2 1
1 2
1 2

输出 #1

YES
NO
YES
YES
NO

注意

在第一个示例中,您可以执行以下操作:

- 在第 $$$1$$$-st 秒内,向 $$$1$$$-st 怪物发射 $$$1$$$ 子弹,并向 $$$3$$$-rd 怪物发射 $$$1$$$ 子弹。然后$$$1$$$-st 怪物死亡,$$$2$$$-nd 和$$$3$$$-rd 怪物靠近;
- 在第 $$$2$$$-nd 秒内,向第 $$$2$$$-nd 怪物发射 $$$2$$$ 子弹。然后第 $$$2$$$-rd 怪物死亡,$$$3$$$-rd 怪物靠近;
- 在第 $$$3$$$-rd 秒内,向 $$$3$$$-rd 怪物发射 $$$2$$$ 子弹。然后$$$3$$$-rd 怪物就死了。

在第二个例子中,你只能发射 $$$1$$$ 子弹,因此你只能在 $$$1$$$-st 秒内杀死两个怪物之一。然后,剩下的怪物靠近并杀死你的角色。