题意概述

有 $N$ 个选手在一条 $300$ 米长的赛道上比赛，赛道分为三段，每段 $100$ 米。
每个选手有一个策略：在第一段、第二段、第三段上的速度（单位：秒/米），速度值范围 $[1,50]$。
赛道上有 $M$ 个加速器，位置已知（距离起点 $1$ 到 $299$ 米）。
当选手到达某个加速器时，如果此时**严格在他前面的人数（包括已到达终点的人）**为 $X$，则他可以以 $1$ 秒/米的速度行驶 $X \bmod 20$ 米（即加速距离），且必须立即使用加速器（不能保留），在加速距离内不能切换回原速度，除非遇到新的加速器。
加速器可重复使用，不失效。
所有选手同时出发，需要计算每个选手到达终点（$300$ 米处）的时间。

关键点分析

1. 加速规则

设选手到达加速器时，前方人数为 $X$（包括已完赛的选手），则获得加速距离 $d = X \bmod 20$ 米，以 $1$ 秒/米的速度行驶这 $d$ 米。
注意：

• $X$ 是严格在他前面的人数，即位置比他更靠前（或已到终点）的选手数。
• 加速距离可能为 $0$（当 $X \bmod 20 = 0$ 时），此时相当于没有加速效果，但仍算“使用”了加速器。
• 加速期间如果遇到下一个加速器，则在到达那个加速器时重新计算 $X$ 并获得新的加速距离，但新加速距离不会叠加，而是替换当前剩余加速距离（因为题目说“有能用的加速器就会用”）。

2. 模拟难点

由于选手速度不同，且加速会影响相对位置，因此前方人数 $X$ 会动态变化。
这需要我们在时间线上精确模拟每个选手的位置变化，并在加速器处更新 $X$。

直接按时间推进模拟（$O(N \cdot T)$）不可行，因为时间单位是秒，最大时间可能达 $300 \times 50 = 15000$ 秒，再乘 $N=20000$ 就太大。

高效模拟方法

事件驱动模拟

我们可以将比赛过程视为一系列事件的发生：

1. 到达加速器事件：某个选手到达某个加速器位置。
2. 加速结束事件：某个选手的加速距离用完，切回原速度。
3. 切换路段事件：选手从一段进入下一段，速度变化。
4. 到达终点事件：选手完成比赛。

初始事件：所有选手从起点出发，按各自第一段速度行驶。

我们需要按事件发生时间顺序处理，并动态更新其他选手的相对位置。

数据结构维护

对于每个选手，维护：

• 当前速度 $v$（秒/米）
• 当前位置 $pos$（米）
• 当前剩余加速距离 $acc\_left$（米，0 表示未在加速）
• 当前路段（1、2、3）

此外，为了快速计算某个选手到达加速器时的 $X$（前方人数），我们需要知道在所有选手中的排名（按位置降序，位置相同时按出发顺序？但这里位置是实数，很少完全相等，若相等则按编号先后）。

维护一个有序数据结构（如平衡树或优先队列），按位置从大到小排序（最前面的人位置最大），支持：

• 查询某个选手的排名（即前面人数）
• 更新选手位置后重新排序

事件时间计算

对于未在加速的选手，其速度固定（由当前路段决定），到达下一个“关键点”的时间可以计算：

• 下一个加速器位置（如果在本路段内）
• 当前路段终点（100、200、300 米）
• 如果正在加速，则加速结束位置

事件时间 = 当前位置 + 剩余加速距离（如果有）或按原速度计算。

算法步骤

1. 读入数据，初始化每个选手的状态（位置 0，速度 = 第一段速度，路段 1，无加速）。
2. 将所有选手按位置放入有序结构（初始位置都为 0，按编号顺序）。
3. 用一个优先队列（小根堆）存储未来事件，事件类型包括：到达加速器、加速结束、切换路段、到达终点。初始事件为每个选手到达第一个加速器（如果第一段有）或到达 100 米处。
4. 循环处理事件，每次取出最早发生的事件：
   • 如果是到达加速器：
     • 计算该选手此时的前方人数 $X$（在有序结构中查询排名）。
     • 加速距离 $d = X \bmod 20$。
     • 如果 $d > 0$，则选手进入加速状态，速度变为 $1$ 秒/米，剩余加速距离 $d$。
     • 如果 $d = 0$，则速度不变。
     • 更新该选手在有序结构中的位置（如果加速，位置可能变化更快）。
     • 安排下一个事件：如果加速距离内会遇到下一个加速器或路段终点，则安排相应事件；否则安排加速结束事件。
   • 如果是加速结束：
     • 恢复选手原路段速度。
     • 安排下一个事件（下一加速器或路段终点）。
   • 如果是切换路段：
     • 更新选手速度到下一路段速度。
     • 安排下一事件。
   • 如果是到达终点：
     • 记录到达时间。
     • 将该选手从有序结构中移除（或标记为已完成）。
5. 处理完所有事件后，输出每个选手的到达时间。

复杂度分析

每个选手最多触发 $O(M + 3)$ 个事件（每个加速器一次 + 路段切换 + 终点），总事件数 $O(N(M+3))$。
每次事件需要查询排名和更新有序结构，若用平衡树（如 std::set 或手写 Treap），每次操作 $O(\log N)$。
总复杂度 $O(N(M+3) \log N)$。
最坏情况 $N=20000$，$M$ 最多 $299$，$O(20000 \cdot 300 \cdot \log 20000) \approx 10^8$ 级别，可能稍慢但可优化（实际许多选手提前完赛，事件数减少）。

实现细节

1. 加速器位置预处理，对每个路段内加速器排序。
2. 选手 ID 与状态映射。
3. 事件比较：先按时间，时间相同则按事件优先级（终点 > 加速结束 > 路段切换 > 到达加速器？需要仔细定义避免循环）。
4. 浮点数精度：位置用 double，时间用 double 或分数，但输出为整数（样例中时间都是整数，可能因为速度是整数且加速距离整数，时间总是整数）。

总结

本题是一个复杂的事件驱动模拟，关键在于：

1. 将过程分解为事件（加速器、路段切换、加速结束、终点）。
2. 使用优先队列按时间处理事件。
3. 维护选手有序结构以快速查询前方人数。
4. 注意加速距离的计算和替换规则。

实现时需要仔细处理事件优先级和状态更新，避免死循环或逻辑错误。