← 返回题目列表

Codeforces · 1409/E

E. 两个平台

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

平面上有 $$$n$$$ 个点。第 $$$i$$$ 点的坐标为 $$$(x_i, y_i)$$$。您有两个水平平台,长度均为 $$$k$$$。每个平台都可以放置在平面上的任何位置,但应水平放置(在相同的 $$$y$$$ 坐标上)并具有整数边框。如果平台的左边界是$$$(x, y)$$$,则右边界是$$$(x + k, y)$$$,边界之间的所有点(包括边界)都属于平台。

请注意,平台可以共享公共点(重叠),并且不必将两个平台放置在相同的 $$$y$$$ 坐标上。

当您将两个平台放在一个平面上时,所有点都开始下落,减少它们的 $$$y$$$ 坐标。如果某个点在某个时刻与某个平台发生碰撞,该点就会停止并被保存。不与任何平台碰撞的点将会丢失。

你的任务是找到如果你以最佳方式放置两个平台,你可以节省的最大点数。

您必须回答 $$$t$$$ 独立测试用例。

为了更好地理解,请阅读下面的注释部分以查看第一个测试用例的图片。

输入

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

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$) — 分别是点的数量和每个平台的长度。测试用例的第二行包含 $$$n$$$ 整数 $$$x_1, x_2, \dots, x_n$$$ ($$$1 \le x_i \le 10^9$$$),其中 $$$x_i$$$ 是第 $$$i$$$ 个点的 $$$x$$$ 坐标。输入的第三行包含 $$$n$$$ 整数 $$$y_1, y_2, \dots, y_n$$$ ($$$1 \le y_i \le 10^9$$$),其中 $$$y_i$$$ 是第 $$$i$$$ 点的 $$$y$$$ 坐标。所有点都是不同的(没有一对 $$$1 \le i < j \le n$$$ 使得 $$$x_i = x_j$$$ 和 $$$y_i = y_j$$$)。

保证$$$n$$$之和不超过$$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)。

输出

对于每个测试用例,打印答案:如果您以最佳方式放置两个平台,则可以节省的最大点数。

示例

输入 #1

4
7 1
1 5 2 3 1 5 4
1 3 6 7 2 5 4
1 1
1000000000
1000000000
5 10
10 7 5 15 8
20 199 192 219 1904
10 10
15 19 8 17 20 10 9 2 10 19
12 13 6 17 1 14 7 9 19 3

输出 #1

6
1
5
10

注意

示例第一个测试用例对应的图片:

蓝点代表点,红线代表平台。一种可能的方法是将第一个平台放置在点 $$$(1, -1)$$$ 和 $$$(2, -1)$$$ 之间,将第二个平台放置在点 $$$(4, 3)$$$ 和 $$$(5, 3)$$$ 之间。向量表示点将如何落下。正如你所看到的,我们唯一无法保存的点是 $$$(3, 7)$$$ 点,因此它会无限下降并丢失。可以证明,我们在这里无法得到更好的答案。另请注意,点 $$$(5, 3)$$$ 根本不会落下,因为它已经在平台上。