「IOI 2023」超车 - 题目

内存限制：2048 MiB 时间限制：2500 ms 标准输入输出

题目类型：传统评测方式：文本比较

上传者： HHOJ

提交提交记录统计测试数据附加文件讨论

从布达佩斯机场到 Forrás 酒店有一条单向单车道的公路，公路的长度为公里。

IOI 2023 活动期间，有辆巴士在这条公路上行驶。巴士从到依次编号。巴士（）计划在活动的第秒从机场出发，行驶一公里用时秒。巴士是备用巴士，行驶一公里用时秒。它从机场出发的时间尚未确定。

巴士在这条公路上行驶时一般不允许超车，但允许在一些被称为调度站的地方进行超车。公路上一共有个调度站（），从到依次编号，位于公路的不同位置。调度站（）的位置在机场出发后沿公路的公里处。调度站按照从机场开始的距离递增排列，也就是对于每个，有。首个调度站设在机场，最后一个设在酒店。也就是说，，。

每辆巴士都以指定的最快速度行驶，除非它遇到前面有比它慢的巴士。在这种情况下，后面的快车会被前面的慢车压着，被迫以慢车的速度行驶。这种情况会持续到两车到达下一个调度站。在那里，快车会完成对慢车的超越。

形式化地说，对于满足且的每组和，巴士到达调度站的时间（以秒为单位）定义如下：对于每个，有。另有。对于满足的每个：

定义巴士到达调度站的期望到达时间 （以秒为单位）为巴士到达调度站之后以全速行驶到达调度站的时间。也就是说，
- 对于每个，有；
- 另有。
巴士到达调度站的时间，是巴士到达调度站的期望到达时间，以及其他比巴士早到调度站的巴士到达调度站的期望到达时间中的最大值。形式化地说，是和所有满足且的中的最大值。

IOI 组委会想要调度备用巴士（巴士）。你的任务是回答组委会的个问题，问题的形式如下：给定备用巴士从机场出发的时间（以秒为单位），它将于何时到达酒店？

你的任务是实现以下函数：

void init(int L, int N, int64[] T, int[] W, int X, int M, int[] S)

int64 arrival_time(int64 Y)

考虑以下调用序列：

init(6, 4, [20, 10, 40, 0], [5, 20, 20, 30], 10, 4, [0, 1, 3, 6])

忽略巴士（它还没有确定出发时间），下表列出了巴士到达每个调度站的期望时间和实际时间：

巴士到达调度站的时间就是它计划从机场出发的时间。也就是说，对于，。

到达调度站的期望时间和实际时间计算如下：

调度站的期望到达时间：
- 巴士：。
- 巴士：。
- 巴士：。
- 巴士：。
调度站的到达时间：
- 巴士和早于巴士到达调度站，所以。
- 巴士早于巴士到达调度站，所以。
- 巴士、巴士和巴士早于巴士到达调度站，所以。
- 没有比巴士更早到达调度站的巴士，所以。

arrival_time(0)

巴士行驶一公里需要秒，现在计划在第秒从机场出发。这种情况下，下表列出每辆巴士的到达时间。常规巴士期望和实际到达时间的唯一变动用下划线标注。

由此可知巴士在第秒到达酒店。因此，函数应该返回。

arrival_time(50)

巴士现在计划在第秒从机场出发。这种情况下，与初始表格相比，常规巴士的到达时间没有变化。下表列出了到达时间。

巴士和较慢的巴士同时到达调度站，然后巴士超过了巴士。接着，巴士在调度站和之间行驶时被巴士压着，导致它到达调度站的时间是第秒，而不是第秒。在过了调度站之后，巴士被巴士压着，直到它们到达酒店。巴士在第秒到达酒店。因此，函数应该返回。

将每辆巴士从机场出发到不同距离的时间画成折线图。图中 x 轴表示从机场出发的距离（以公里为单位），y 轴表示时间（以秒为单位）。竖的虚线标注了调度站的位置。不同颜色的实线（标注了巴士的编号）表示四辆常规巴士。黑色的点线表示备用巴士。

`arrival_time(0)`	`arrival_time(50)`

评测程序示例按以下格式读取输入：

评测程序示例按以下格式打印你的答案：

编辑器加载中 …

或者，上传代码文件

#2034. 「IOI 2023」超车