P11118 [ROI 2024] 无人机比赛 (Day 2)

翻译自 [ROI 2024 D2T3](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day2.pdf)。 有 $n$ 架无人机报名参加一个无人机比赛，第 $i$ 架无人机飞过一单位距离需要 $t_i$ 秒。 比赛在一条直线上进行，该直线上有 $m$ 个门，编号从 $1$ 到 $m$，第 $i$ 个门位于距离比赛起点 $s_i$ 的位置。 因为赛道大小的限制，第一场比赛只会有前 $k$ 架无人机参与，编号从 $1$ 到 $k$。$k$ 的值由裁判在比赛开始前宣布，因此此时你需要对 $k$ 从 $1$ 到 $n$ 的比赛情况进行分析。 比赛的进行方式如下： 无人机从 $0$ 号点开始向门移动，每架无人机的速度不同。每架无人机都有一个存档点，即最后一个它进行了存档操作的门。最初，每架无人机的存档点都是 $0$ 号点。 在比赛中，所有无人机从其存档点开始移动，直到有一架或多架无人机到达一个门（有可能是不同无人机同时到达不同的门）。此时，在所有到达门的无人机中，选择编号最小的无人机，对该无人机进行存档操作，将其存档点设置为当前的位置。其他无人机立即传送到其存档点。然后，比赛继续进行。 如果一架无人机在最后一个编号为 $m$ 的门上进行存档操作，那么它就完成了比赛。尚未完成的无人机将传送到其存档点继续比赛。当所有无人机都完赛时，比赛结束。

传送是一个非常耗能的过程。为了准备比赛，你需要了解所有无人机在比赛结束之前一共将进行多少次传送。设 $c_k$ 表示当前 $k$ 架无人机参与比赛时，所有无人机的总传送次数，则你需要求出 $c_1, c_2, \dots, c_n$ 的值。

无

无

样例 $1$ 解释： 当 $k=1$，无需任何传送，因为只有一架无人机参加，只有它在一直存档。 当 $k=2$ 时，整个比赛的过程如下图所示。  当 $k=3$ 时，整个比赛的过程如下图所示。  各子任务特殊性质表格： | 子任务 | 分值 | $n\le$ | $m\le$ | $t_i\le$ | $s_i\le$ | 其它特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $5$ | $2$ | $50$ | $100000$ | $100000$ | | | $2$ | $7$ | $50$ | $50$ | $100000$ | $100000$ | | | $3$ | $13$ | $1000$ | $5$ | $100000$ | $100000$ | | | $4$ | $9$ | $100000$ | $100000$ | $100000$ | $100000$ | $s_{i+1}-s_i=s_1$ | | $5$ | $8$ | $100000$ | $100000$ | $100000$ | $100000$ | 所有 $t_i$ 相等 | | $6$ | $10$ | $100$ | $100000$ | $100000$ | $100000$ | | | $7$ | $5$ | $100000$ | $100000$ | $2$ | $100000$ | | | $8$ | $7$ | $100000$ | $m=2$ | $100000$ | $100000$ | | | $9$ | $6$ | $10000$ | $100000$ | $100000$ | $100000$ | | | $10$ | $6$ | $50000$ | $100000$ | $100000$ | $100000$ | | | $11$ | $8$ | $100000$ | $100000$ | $100000$ | $100000$ | | | $12$ | $8$ | $100000$ | | | | | | $13$ | $8$ | | | | | |