题目描述

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

IOI 2023 期间，有 $N+1$ 辆巴士在这条公路上行驶，编号为 $0$ 到 $N$。其中：

• 巴士 $i$（$0 \le i < N$）计划在第 $T[i]$ 秒从机场出发，行驶 $1$ 公里用时 $W[i]$ 秒。
• 巴士 $N$ 是备用巴士，行驶 $1$ 公里用时 $X$ 秒，出发时间 $Y$ 待定。

公路上有 $M$ 个调度站（$M > 1$），编号 $0$ 到 $M-1$，位于不同位置：

• 调度站 $j$（$0 \le j < M$）距离机场 $S[j]$ 公里，且 $S[0] = 0$（机场），$S[M-1] = L$（酒店），满足 $S[0] < S[1] < \cdots < S[M-1]$。

巴士行驶规则

巴士以最快速度行驶，但若被前方慢车阻挡，需以慢车速度行驶，直到下一个调度站完成超车。形式化定义巴士 $i$ 到达调度站 $j$ 的时间 $t_{i,j}$ 如下：

1. 初始条件：对 $0 \le i < N$，$t_{i,0} = T[i]$；对备用巴士 $N$，$t_{N,0} = Y$。
2. 期望到达时间 $e_{i,j}$（$0 < j < M$）：
   • 常规巴士：$e_{i,j} = t_{i,j-1} + W[i] \cdot (S[j] - S[j-1])$；
   • 备用巴士：$e_{N,j} = t_{N,j-1} + X \cdot (S[j] - S[j-1])$。
3. 实际到达时间 $t_{i,j}$：$e_{i,j}$ 与所有“比巴士 $i$ 早到达调度站 $j-1$ 的巴士的 $e_{k,j}$”中的最大值，即：$$t_{i,j} = \max\left( e_{i,j}, \max\left\{ e_{k,j} \mid 0 \le k \le N, \, t_{k,j-1} < t_{i,j-1} \right\} \right) $$

你的任务是回答 $Q$ 个查询：给定备用巴士的出发时间 $Y$，返回其到达酒店（调度站 $M-1$）的时间。

实现细节

需在程序开始引入库 overtaking.h，并实现以下函数：

1. 初始化函数

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

• 参数：
  • $L$：公路长度；
  • $N$：常规巴士数量；
  • $T$：长度为 $N$ 的数组，常规巴士的出发时间；
  • $W$：长度为 $N$ 的数组，常规巴士的每公里耗时；
  • $X$：备用巴士的每公里耗时；
  • $M$：调度站数量；
  • $S$：长度为 $M$ 的数组，调度站位置（公里）。
• 说明：每个测试用例仅调用一次，在所有 arrival_time 调用前执行。

2. 查询函数

int64 arrival_time(int64 Y)

• 参数：$Y$ 为备用巴士的出发时间；
• 返回：备用巴士到达酒店的时间；
• 说明：每个测试用例调用 $Q$ 次。

例子

初始化调用

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

常规巴士到达各调度站的时间如下表（忽略备用巴士时）：

$i$	$t_{i,0}$	$e_{i,1}$	$t_{i,1}$	$e_{i,2}$	$t_{i,2}$	$e_{i,3}$	$t_{i,3}$
$0$	$20$	$25$	$30$	$40$		$55$
$1$	$10$	$30$		$70$		$130$
$2$	$40$	$60$		$100$		$160$	$180$
$3$	$0$	$30$		$90$		$180$

查询 1：arrival_time(0)

备用巴士出发时间 $Y=0$，其到达时间如下：

$i=4$	$t_{4,0}=0$	$e_{4,1}=10$	$t_{4,1}=10$	$e_{4,2}=30$	$t_{4,2}=30$	$e_{4,3}=60$	$t_{4,3}=60$

返回 $60$。

查询 2：arrival_time(50)

备用巴士出发时间 $Y=50$，其到达时间如下：

$i=4$	$t_{4,0}=50$	$e_{4,1}=60$	$t_{4,1}=60$	$e_{4,2}=80$	$t_{4,2}=90$	$e_{4,3}=120$	$t_{4,3}=130$

返回 $130$。

约束条件

• $1 \le L \le 10^9$；
• $1 \le N \le 1000$；
• $0 \le T[i] \le 10^{18}$（$0 \le i < N$）；
• $1 \le W[i] \le 10^9$（$0 \le i < N$）；
• $1 \le X \le 10^9$；
• $2 \le M \le 1000$；
• $0 = S[0] < S[1] < \cdots < S[M-1] = L$；
• $1 \le Q \le 10^6$；
• $0 \le Y \le 10^{18}$。

子任务

子任务	附加限制	分值
1	$N=1$，$Q \le 1000$	$9$
2	$M=2$，$Q \le 1000$	$10$
3	$N, M, Q \le 100$	$20$
4	$Q \le 5000$	$26$
5	无额外约束	$35$

评测程序示例

输入格式

1. 第 $1$ 行：$L \; N \; X \; M \; Q$；
2. 第 $2$ 行：$T[0] \; T[1] \; \ldots \; T[N-1]$；
3. 第 $3$ 行：$W[0] \; W[1] \; \ldots \; W[N-1]$；
4. 第 $4$ 行：$S[0] \; S[1] \; \ldots \; S[M-1]$；
5. 第 $5+k$ 行（$0 \le k < Q$）：查询 $k$ 的 $Y$ 值。

输出格式

第 $1+k$ 行（$0 \le k < Q$）：查询 $k$ 的返回值（备用巴士到达酒店的时间）。