难度估计：CF 2600～2800

题目描述

皇家信使需要尽快从点 $A$ 到达点 $B$。点 $A$ 在数轴上的坐标为 $0$，点 $B$ 的坐标为正整数 $B$。

在 $A$ 到 $B$ 的直线上有 $N$ 个马厩。第 $i$ 个马厩位于位置 $X_i$，其中有 $M_i$ 匹马。

每匹马由两个参数描述：

• 速度 $v$；
• 最大奔跑距离 $d$。

信使骑上一匹马后，最多可以让它奔跑 $d$ 的距离，之后这匹马会精疲力尽。只要信使到达或经过某个马厩，就可以立即换乘该马厩中的任意一匹马，换马不消耗时间。

信使不允许步行。

求从 $0$ 到达 $B$ 的最短时间。

输入格式

第一行包含两个整数 $B,N$：

• $1\le B\le 10^8$；
• $1\le N\le 5000$。

接下来依次描述 $N$ 个马厩。

每个马厩的第一行包含两个整数 $X_i,M_i$：

• $0\le X_i\le 10^8$；
• $M_i>0$。

随后 $M_i$ 行，每行两个整数 $v_j,d_j$，描述一匹马：

• $1\le v_j\le 10^8$；
• $1\le d_j\le 10^8$。

所有马厩中的马匹总数不超过 $10^5$。

允许多个马厩位于同一位置。

输出格式

输出信使到达 $B$ 所需的最短时间，要求小数点后至少保留 $3$ 位精度。

如果无法到达 $B$，输出 -1。

样例

10 3
5 2
1 100
10 3
0 1
1 50
8 1
2 3

6.30000000

算法要点

将马厩按位置排序，设 $dp[i]$ 表示到达第 $i$ 个马厩的最短时间。

若在位置 $x_i$ 使用速度为 $v$、耐力距离为 $d$ 的马，则它可以到达所有满足 $x_j\le x_i+d$ 的后继马厩，转移为：

$dp[j]=\min\left(dp[j],\ dp[i]+\frac{x_j-x_i}{v}\right)$。

把式子改写成关于 $x_j$ 的一次函数：

$dp[i]-\frac{x_i}{v}+\frac{1}{v}x_j$。

因此每匹马对应一条直线，但这条直线只对一段连续的马厩下标有效。问题转化为：

• 区间加入一条直线；
• 单点查询该位置所有有效直线的最小值。

使用“线段树套动态凸包”即可完成。每条直线被加入 $O(\log N)$ 个线段树节点，每次查询沿根到叶路径查询 $O(\log N)$ 个凸包。

总复杂度约为 $O(H\log N\log H)$，其中 $H\le 10^5$ 为马匹总数。