说明

\\n\\n小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条长度为 $L$ 的南北主干道的车辆超速检测。为了考考小 D，上司首先需要他解决一个简化的场景。 \\n\\n这个周末，主干道上预计出现 $n$ 辆车，其中第 $i$ 辆车从主干道上距离最南端 $d_i$ 的位置驶入，以 $v_i$ 的初速度和 $a_i$ 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆，故 $v_i > 0$，但 $a_i$ 可正可负，也可以为零。当车辆行驶到主干道最北端（即距离最南端为 $L$ 的位置）或速度降为 $0$（这只可能在 $a_i < 0$ 时发生）时，我们认为该车驶离主干道。 \\n\\n主干道上设置了 $m$ 个测速仪，其中第 $j$ 个测速仪位于主干道上距离最南端 $p_j$ 的位置，每个测速仪可以设置开启或关闭。当某辆车经过某个开启的测速仪时，若这辆车的瞬时速度超过了道路限速 $V$，那么这辆车就会被判定为超速。注意当车辆驶入与驶出主干道时，如果在对应位置有一个开启的测速仪，这个测速仪也会对这辆车进行测速。 \\n\\n上司首先想知道，如果所有测速仪都是开启的，那么这 $n$ 辆车中会有多少辆车被判定为超速。 \\n\\n其次，为了节能，部门想关闭一部分测速仪。然而，他们不希望漏掉超速的车，也就是说，当 $n$ 辆车里的某辆车在所有测速仪都开启时被判定为超速，他们希望在关闭一部分测速仪以后它依然被判定为超速。上司还想知道在这样的条件下最多可以关闭多少测速仪。 \\n\\n由于 $n$ 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。 \\n\\n如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速度的公式。\\n\\n

输入格式

\\n\\n输入的第一行包含一个正整数 $T$，表示数据组数。 \\n\\n接下来包含 $T$ 组数据，每组数据的格式如下： \\n\\n第一行包含四个整数 $n, m, L, V$，分别表示车辆数量、测速仪数量、主干道长度和道路限速。 \\n\\n接下来 $n$ 行： \\n\\n第 $i$ 行包含三个整数 $d_i, v_i, a_i$ 描述一辆车。 \\n\\n最后一行包含 $m$ 个整数 $p_1, p_2, \\\\dots , p_m$ 描述道路上所有测速仪的位置。\\n\\n

输出格式

\\n\\n对于每组数据：输出一行包含两个整数，第一个整数为所有测速仪都开启时被判定为超速的车辆数量，第二个整数为在不漏掉超速车辆的前提下最多可以关闭的测速仪数量。\\n\\n

样例

\\n\\n

状态	递交者	时间	内存	语言	代码	递交时间
AC	张泊文	2691ms	16.4 MiB	C++20(O2)	2.2 KiB	2026-10-11 17:26:39
AC	邓泊修	3259ms	16.4 MiB	C++14(O2)	1.2 KiB	2026-10-11 16:47:55
AC	刘星辰	3454ms	16.4 MiB	C++20(O2)	1.1 KiB	2026-10-11 23:57:38

统计

递交统计

[CSP-S 2024] 超速检测

信息

状态

开发

支持

关于

登录