5542: 2024 [CSP-S]超速检测
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 L 的南
北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。
这个周末，主干道上预计出现 n 辆车，其中第 i 辆车从主干道上距离最南端 di 的
位置驶入，以 vi 的初速度和 ai 的加速度做匀加速运动向北行驶。我们只考虑从南向北
的车辆，故 vi > 0，但 ai 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离
最南端为 L 的位置）或速度降为 0（这只可能在 ai < 0 时发生）时，我们认为该车驶离
主干道。
主干道上设置了 m 个测速仪，其中第 j 个测速仪位于主干道上距离最南端 pj 的位
置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的
瞬时速度超. 过. 了道路限速 V ，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主
干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。
上司首先想知道，如果所有测速仪都是开启的，那么这 n 辆车中会有多少辆车被判
定为超速。
其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也
就是说，当 n 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一
部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少
测速仪。
由于 n 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。
如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速
度的公式
输入
从文件 detect.in 中读入数据。
本. 题. 有. 多. 组. 测. 试. 数. 据。.
输入的第一行包含一个正整数 T，表示数据组数。
接下来包含 T 组数据，每组数据的格式如下：
第一行包含四个整数 n, m, L, V ，分别表示车辆数量、测速仪数量、主干道长度和
道路限速。
接下来 n 行：
第 i 行包含三个整数 di , vi , ai 描述一辆车。
最后一行包含 m 个整数 p1, p2, · · · , pm 描述道路上所有测速仪的位置。
输出
输出到文件 detect.out 中。
对于每组数据：输出一行包含两个整数，第一个整数为所有测速仪都开启时被判定
为超速的车辆数量，第二个整数为在不漏掉超速车辆的前提下最多可以关闭的测速仪数
量。
样例输入 复制
1
5 5 15 3
0 3 0
12 4 0
1 1 4
5 5 ‐2
6 4 ‐4
2 5 8 9 15
样例输出 复制
3 3
提示
【样例 1 解释】
在该组测试数据中，主干道长度为 15，限速为 3，在距离最南端 2, 5, 8, 9, 15 的位置
各设有一个测速仪。
• 第一辆车在最南端驶入，以 3 的速度匀速行驶。这辆车在整个路段上都没有超速。
• 第二辆车在距离最南端 12 的位置驶入，以 4 的速度匀速行驶。在最北端驶离主
干道时，它会被距离最南端 15 的测速仪判定为超速。
• 第三辆车在距离最南端 1 的位置驶入，以 1 的初速度、4的加速度行驶。其在行
驶了
的距离，即到达 2 的位置时，速度变为 3，并在之后一直超速。因
此这辆车会被除了距离最南端 2 的测速仪以外的其他测速仪判定为超速。
• 第四辆车在距离最南端 5 的位置驶入，以 5 的初速度、−2 的加速度行驶。其在
行驶了
的距离，即到达 9 的位置时，速度变为 3。因此这辆车在距离
最南端 [5, 9) 时超速，会被距离最南端 5 和 8 的两个测速仪判定为超速。
• 第五辆车在距离最南端 6 的位置驶入，以 4 的初速度、−4 的加速度行驶。在其
行驶了
的距离后，即这辆车到达
的位置时，其速度变为 3。因此
这辆车在距离最南端
时超速，但这段区间内没有测速仪，因此不会被判定
为超速。
因此第二、三、四辆车会被判定为超速，输出的第一个数为 3。
我们可以关闭距离最南端 2, 8, 9 的三个测速仪，保留 5 和 15 的两个测速仪，此时
三辆之前被判定为超速的车依然被判定为超速。可以证明不存在更优方案，因此输出的
第二个数为 3。
【样例 2】
见选手目录下的 detect/detect2.in 与 detect/detect2.ans。
该组样例满足 n, m ≤ 10。
【样例 3】
见选手目录下的 detect/detect3.in 与 detect/detect3.ans。
该组样例满足特殊性质 A，其中前十组测试数据满足 n, m ≤ 3000。
【样例 4】
见选手目录下的 detect/detect4.in 与 detect/detect4.ans。
该组样例满足特殊性质 B，其中前十组测试数据满足 n, m ≤ 3000。
【样例 5】
见选手目录下的 detect/detect5.in 与 detect/detect5.ans。
该组样例满足特殊性质 C，其中前十组测试数据满足 n, m ≤ 3000。
特殊性质 A：保证 ai = 0。
特殊性质 B：保证 ai > 0。
特殊性质 C：保证 ai < 0，且所有车都不在最北端驶离主干道。
【提示】
与加速度有关的定义和公式如下：
• 匀加速运动 是指物体在运动过程中，加速度保持不变的运动，即每单位时间内
速度的变化量是恒定的。
• 当一辆车的初速度为 v0、加速度 a = 0，做匀加速运动，则 t 时刻后它的速度
v1 = v0 + a × t，它的位移（即行驶路程）s = v0 × t + 0.5 × a × t 2。
• 当一辆车的初速度为 v0、加速度 a = 0，做匀加速运动，则当它的位移（即行驶
路程）为 s 时，这辆车的瞬时速度为 
• 当一辆车的初速度为 v0、加速度 a ≠ 0，在它的位移（即行驶路程）为
时，
时，
这辆车的瞬时速度为 v1。
如果你使用浮点数进行计算，需要注意潜在的精度问题。