A4701 | [CSP-S 2024] 超速检测

• 第一辆车在最南端驶入，以 $3$ 的速度匀速行驶。这辆车在整个路段上都没有超速。
• 第二辆车在距离最南端 $12$ 的位置驶入，以 $4$ 的速度匀速行驶。在最北端驶离主干道时，它会被距离最南端 $15$ 的测速仪判定为超速。
• 第三辆车在距离最南端 $1$ 的位置驶入，以 $1$ 的初速度、$4$ 的加速度行驶。其在行驶了 $\frac{3^2-1^2}{2\times 4}=1$ 的距离，即到达 $2$ 的位置时，速度变为 $3$，并在之后一直超速。因此这辆车会被除了距离最南端 $2$ 的测速仪以外的其他测速仪判定为超速。
• 第四辆车在距离最南端 $5$ 的位置驶入，以 $5$ 的初速度、$-2$ 的加速度行驶。其在行驶了 $\frac{3^2-5^2}{2\times (-2)}$ 的距离，即到达 $9$ 的位置时，速度变为 $3$。因此这辆车在距离最南端 $[5, 9)$ 时超速，会被距离最南端 $5$ 和 $8$ 的两个测速仪判定为超速。
• 第五辆车在距离最南端 6 的位置驶入，以 4 的初速度、−4 的加速度行驶。在其行驶了 $\frac{3^2-4^2}{2\times (-4)}=\frac{7}{8}$ 的距离后，即这辆车到达 $6\frac{7}{8}$ 的位置时，其速度变为 $3$。因此这辆车在距离最南端 $[6,6\frac{7}{8})$ 时超速，但这段区间内没有测速仪，因此不会被判定为超速。

因此第二、三、四辆车会被判定为超速，输出的第一个数为 $3$。

我们可以关闭距离最南端 $2, 8, 9$ 的三个测速仪，保留 $5$ 和 $15$ 的两个测速仪，此时三辆之前被判定为超速的车依然被判定为超速。可以证明不存在更优方案，因此输出的第二个数为 $3$。

【样例 2】

见选手目录下的 detect/detect2.in 与 detect/detect2.ans。

该组样例满足 $n, m \leq 10$。

【样例 3】

见选手目录下的 detect/detect3.in 与 detect/detect3.ans。

该组样例满足特殊性质 A，其中前十组测试数据满足 $n, m \leq 3000$。

【样例 4】

见选手目录下的 detect/detect4.in 与 detect/detect4.ans。

该组样例满足特殊性质 B，其中前十组测试数据满足 $n, m \leq 3000$。

【样例 5】

见选手目录下的 detect/detect5.in 与 detect/detect5.ans。

该组样例满足特殊性质 C，其中前十组测试数据满足 $n, m \leq 3000$。

【数据范围】

对于所有测试数据，保证：

• $1 \leq T \leq 20$；
• $1 \leq n, m \leq 10^5$，$1 \leq L \leq 10^6$，$1 \leq V \leq 10^3$；
• $0 \leq d_i L$，$1 \leq v_i \leq 10^3$，$|a_i| \leq 10^3$；
• $0 \leq p_1 p_2 \dots p_m \leq L$。



测试点	$n,m\leq$	特殊性质
$1$	$10$	无
$2$	$20$	无
$3$	$3000$	A
$4$	$10^5$	A
$5$	$3000$	B
$6$	$10^5$	B
$7$	$3000$	C
$8$	$10^5$	C
$9$	$3000$	无
$10$	$10^5$	无



特殊性质 A：保证 $a_i = 0$。

特殊性质 B：保证 $a_i 0$。

特殊性质 C：保证 $a_i 0$，且所有车都不在最北端驶离主干道。

【提示】

与加速度有关的定义和公式如下：

• 匀加速运动是指物体在运动过程中，加速度保持不变的运动，即每单位时间内速度的变化量是恒定的。
• 当一辆车的初速度为 $v_0$、加速度 $a\neq 0$，做匀加速运动，则 $t$ 时刻后它的速度 $v_1 = v_0 + a \times t$，它的位移（即行驶路程）$s=v_0\times t+0.5\times a\times t^2$。
• 当一辆车的初速度为 $v_0$、加速度 $a \neq 0$，做匀加速运动，则当它的位移（即行驶路程）为 $s$ 时，这辆车的瞬时速度为 $\sqrt{v_0^2+2\times a\times s}$。
• 当一辆车的初速度为 $v_0$、加速度 $a \neq 0$，在它的位移（即行驶路程）为 $\frac{v_1^2-v_0^2}{2a}$ 时，这辆车的瞬时速度为 $v_1$。

附件下载