#P12537. [XJTUPC 2025] 罗斯飞鸽

    ID: 14090 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>动态规划 DP二分2025O2优化高校校赛

[XJTUPC 2025] 罗斯飞鸽

题目描述

awa 正在参加一个叫做罗斯飞鸽的真人音游活动。在活动中,awa 要在指定的时间出现在指定的位置。

具体来说,罗斯飞鸽的活动场地是一条无限长的直线。罗斯飞鸽一共有 nn 个判定点。第 ii 个判定点要求 awa 在时刻 tit_i 出现在位置 xix_i

awa 的最大跑步速度是 vv 个单位每时刻。在时刻 00,awa 可以任意选择一个位置,随后开始游玩罗斯飞鸽。

awa 想知道,自己最多能够达成多少个判定点。

输入格式

第一行一个正整数 TT (1T5×1051\le T \le 5\times 10^5),表示 awa 一共进行了 TT 次游戏。

对于每次游戏,第一行两个正整数 nnvv (1n5×1051\le n \le 5\times 10^5, 1v1091 \le v \le 10^9),用一个空格分隔,表示判定点的数量和 awa 的最大速度。

接下来 nn 行,每行两个整数 tit_ixix_i (0ti,xi1090 \le t_i, |x_i| \le 10^9),用一个空格分隔,描述一个判定点。保证一局游戏中没有两个完全相同的判定点。

保证 TT 轮游戏中 nn 的总和不超过 5×1055 \times 10^5

输出格式

一共 TT 行,每行一个整数,表示对应游戏中 awa 最多能达成多少个判定点。

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