CF730D Running Over The Bridges

Polycarp 正在玩一个叫做“跨桥跑酷”的游戏。在这个游戏中，他需要从左到右依次跨越 $n$ 座桥。所有桥是一座接着一座排列的，第 $i$ 座桥的起点正好是第 $i-1 $ 座桥的终点。 你得到了以下关于每座桥的信息：$l_{i}$ 表示第 $i$ 座桥的长度，$t_{i}$ 表示 Polycarp 在第 $i$ 座桥上最多能停留的时间。也就是说，如果 Polycarp 在时间 $T$ 到达第 $i$ 座桥的起点，他必须在时间 $T+t_{i}$ 或之前离开该桥。允许恰好在时间 $T+t_{i}$ 到达桥的终点。 Polycarp 平时的速度为 $0.5$，所以他要用 $2·s$ 秒才能跑完长度为 $s$ 的桥。此外，他有若干瓶魔法饮料。如果喝下一瓶，他的速度会提升一倍（即变为 1），持续 $r$ 秒。所有的魔法饮料效果完全相同。请注意，Polycarp 只能在整数时刻喝饮料，每次必须一口气喝完。同时，如果 Polycarp 在时刻 $T$ 喝了饮料，那么下一次喝饮料不早于 $T+r$。 请你求出 Polycarp 至少需要喝多少瓶饮料，才能在规定时间内跨过全部 $n$ 座桥。如果答案不超过 $10^5$，还要求出他每次喝饮料的具体时间。

第一行包含两个整数 $n$ 和 $r$（$1 \leq n \leq 2·10^5$，$1 \leq r \leq 10^{12}$）——表示桥的数量和每瓶饮料的效果持续时间。 第二行包含 $l_1, l_2, \ldots, l_n$（$1 \leq l_i \leq 5·10^6$），表示每座桥的长度。 第三行包含 $t_1, t_2, \ldots, t_n$（$1 \leq t_i \leq 10^7$），表示每座桥允许通过的最大时间。

第一行输出 $k$——Polycarp 需要喝饮料的最少次数。如果无解，输出 $-1$。 如果存在解且 $k \leq 10^5$，则在第二行输出 $k$ 个整数，表示他喝每一瓶饮料的时刻（从游戏开始计时），按时间顺序排列。如果有多组答案可行，输出任意一组即可。

在第一个样例中，只有一座桥，很明显 Polycarp 如果不喝魔法饮料无法及时通过。因此，如果他在起点（时刻 $0$）喝下第一瓶，在三秒后（时刻 $3$）喝第二瓶，就能及时通过这座桥。需要注意，本题的答案可能有多种。例如，他也可以在时刻 $4$ 喝第一瓶，时刻 $7$ 喝第二瓶。 在第二个样例中，即使 Polycarp 一直使用魔法饮料，也无法及时跨越所有桥。因此输出 $-1$。 在第四个样例中，Polycarp 不用喝饮料就能通过所有桥。 由 ChatGPT 5 翻译