← 返回题目列表

Codeforces · 1469/C

C. 建造围栏

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

您想要建造一个由 $$$n$$$ 相等部分组成的栅栏。所有部分的宽度等于 $$$1$$$,高度等于 $$$k$$$。您将所有部分并排放置在一行中。

不幸的是,栅栏下面的地面并不平坦。为简单起见,您可以认为第 $$$i$$$ 部分下的地面等于 $$$h_i$$$。

建造围栏时应遵循以下几条规则:

1. 连续的部分应具有长度至少$$$1$$$的公共边;
2. 第一个和最后一个部分应位于相应的地面上;
3. 其间的部分可以位于地面或更高,但距地面 $$$h_i$$$ 的高度不得高于 $$$k - 1$$$(高度应为整数);

第一个测试用例的可能围栏之一(蓝色)

是否可以建造符合所有规则的围栏?

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$2 \le k \le 10^8$$$) - 围栏中的部分数量和每个部分的高度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \dots, h_n$$$ ($$$0 \le h_i \le 10^8$$$),其中 $$$h_i$$$ 是第 $$$i$$$ 部分下方的地面水平。

保证测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以构建满足所有规则的栅栏,则打印“是”。否则,打印NO。

您可以在任何情况下打印每个字母(例如,YES,Yes,yes,yE 都将被识别为肯定答案)。

示例

输入 #1

3
6 3
0 0 2 5 1 1
2 3
0 2
3 2
3 0 2

输出 #1

YES
YES
NO

注意

在第一个测试用例中,图中显示了一个可能的围栏。

在第二个测试用例中,根据第二条规则,您应该在相应的地面上构建两个部分,并且由于 $$$k = 3$$$、$$$h_1 = 0$$$ 和 $$$h_2 = 2$$$ 也满足第一条规则。

在第三个测试用例中,根据第二条规则,您应该在高度 $$$3$$$ 上构建第一部分,在高度 $$$2$$$ 上构建第三部分。根据第一条规则,第二部分的高度应至少为 $$$2$$$(与第一部分有公共边),但根据第三条规则,第二部分的高度最多可达 $$$h_2 + k - 1 = 1$$$。