P9604 [IOI 2023] Overtaking

This is an interactive problem. You only need to implement the functions required in the code. Your code does not need to include any additional header files, and you do not need to implement the `main` function. This problem only supports submissions in C++. However, please do not use C++14 (GCC 9).

There is a one-way, single-lane road from Budapest Airport to the Forrás Hotel, and the road has length $L$ kilometers. During IOI 2023, there are $N+1$ buses driving on this road. The buses are numbered from $0$ to $N$. Bus $i$ ($0 \le i \lt N$) is planned to depart from the airport at second $T[i]$, and it needs $W[i]$ seconds to travel one kilometer. Bus $N$ is a spare bus; it needs $X$ seconds to travel one kilometer. Its departure time $Y$ from the airport is not determined yet. On this road, overtaking is normally not allowed, but it is allowed at some places called **dispatch stations**. There are $M$ dispatch stations ($M \gt 1$), numbered from $0$ to $M - 1$, located at distinct positions on the road. Dispatch station $j$ ($0 \le j \lt M$) is located at $S[j]$ kilometers from the airport along the road. The dispatch stations are listed in increasing order of distance from the airport, i.e., for every $0 \le j \le M - 2$, we have $S[j] \lt S[j+1]$. The first dispatch station is at the airport and the last one is at the hotel. That is, $S[0] = 0$ and $S[M-1] = L$. Each bus drives at its maximum speed unless it encounters a slower bus in front of it. In that case, the faster bus behind is blocked by the slower bus and is forced to drive at the slower bus's speed. This continues until both buses reach the next dispatch station, where the faster bus overtakes the slower one. Formally, for each pair $i$ and $j$ such that $0 \le i \le N$ and $0 \le j \lt M$, the time $t_{i,j}$ (in seconds) when bus $i$ **arrives** at dispatch station $j$ is defined as follows: for each $0 \le i \lt N$, we have $t_{i,0} = T[i]$. Also, $t_{N,0} = Y$. For each $j$ such that $0 \lt j \lt M$: * Define the **expected arrival time** $e_{i,j}$ (in seconds) of bus $i$ at dispatch station $j$ as the time when bus $i$ reaches dispatch station $j$ if it drives at full speed after arriving at dispatch station $j-1$. That is, - for each $0 \le i \lt N$, $e_{i,j} = t_{i,j-1} + W[i] \cdot (S[j]-S[j-1])$; - and $e_{N,j} = t_{N,j-1} + X \cdot (S[j]-S[j-1])$. * The arrival time of bus $i$ at dispatch station $j$ is the **maximum** of the expected arrival time of bus $i$ at dispatch station $j$, and the expected arrival times at dispatch station $j$ of all other buses that arrived at dispatch station $j-1$ earlier than bus $i$. Formally, $t_{i,j}$ is the maximum of $e_{i,j}$ and all $e_{k,j}$ such that $0 \le k \le N$ and $t_{k,j-1} \lt t_{i,j-1}$. The IOI committee wants to schedule the spare bus (bus $N$). Your task is to answer $Q$ queries from the committee, each of the following form: given the departure time $Y$ (in seconds) of the spare bus from the airport, when will it arrive at the hotel?

The sample grader reads input in the following format: * Line $1$: $L \; N \; X \; M \; Q$ * Line $2$: $T[0] \; T[1] \; \ldots \; T[N-1]$ * Line $3$: $W[0] \; W[1] \; \ldots \; W[N-1]$ * Line $4$: $S[0] \; S[1] \; \ldots \; S[M-1]$ * Line $5 + k$ ($0 \le k \lt Q$): the value $Y$ for query $k$

The sample grader prints your answers in the following format: * Line $1 + k$ ($0 \le k \lt Q$): the return value of `arrival_time` for query $k$

**[Implementation details]** Your task is to implement the following functions: ``` void init(int L, int N, int64[] T, int[] W, int X, int M, int[] S) ``` * $L$: the length of the road * $N$: the number of regular (non-spare) buses * $T$: an array of length $N$, describing the planned departure times of the regular buses from the airport. * $W$: an array of length $N$, describing the maximum speeds of the regular buses. * $X$: the time (in seconds) the spare bus needs to travel one kilometer * $M$: the number of dispatch stations * $S$: an array of length $M$, describing the distances from the airport to the dispatch stations. * For each test case, this function is called exactly once, before any call to `arrival_time`. ``` int64 arrival_time(int64 Y) ``` * $Y$: the planned departure time of the spare bus (bus $N$) from the airport * This function should return the time when the spare bus arrives at the hotel. * This function is called exactly $Q$ times. --- **[Example]** Consider the following call sequence: ``` init(6, 4, [20, 10, 40, 0], [5, 20, 20, 30], 10, 4, [0, 1, 3, 6]) ``` Ignoring bus $4$ (since its departure time has not been determined yet), the table below lists the expected and actual arrival times of the buses at each dispatch station: | $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$ | $40$ | | $55$ | $55$ | | $1$ | | $10$ | | $30$ | $30$ | | $70$ | $70$ | | $130$ | $130$ | | $2$ | | $40$ | | $60$ | $60$ | | $100$ | $100$ | | $160$ | $180$ | | $3$ | | $0$ | | $30$ | $30$ | | $90$ | $90$ | | $180$ | $180$ | The time when a bus arrives at dispatch station $0$ is exactly its planned departure time from the airport. That is, for $0 \le i \le 3$, $t_{i,0} = T[i]$. The expected and actual arrival times at dispatch station $1$ are computed as follows: * Expected arrival times at dispatch station $1$: - Bus $0$: $e_{0,1} = t_{0,0} + W[0] \cdot (S[1]-S[0]) = 20 + 5 \cdot 1 = 25$. - Bus $1$: $e_{1,1} = t_{1,0} + W[1] \cdot (S[1]-S[0]) = 10 + 20 \cdot 1 = 30$. - Bus $2$: $e_{2,1} = t_{2,0} + W[2] \cdot (S[1]-S[0]) = 40 + 20 \cdot 1 = 60$. - Bus $3$: $e_{3,1} = t_{3,0} + W[3] \cdot (S[1]-S[0]) = 0 + 30 \cdot 1 = 30$. * Arrival times at dispatch station $1$: - Buses $1$ and $3$ arrived at dispatch station $0$ earlier than bus $0$, so $t_{0,1} = \max([e_{0,1},e_{1,1},e_{3,1}]) = 30$. - Bus $3$ arrived at dispatch station $0$ earlier than bus $1$, so $t_{1,1} = \max([e_{1,1},e_{3,1}]) = 30$. - Buses $0$, $1$, and $3$ arrived at dispatch station $0$ earlier than bus $2$, so $t_{2,1} = \max([e_{0,1},e_{1,1},e_{2,1},e_{3,1}]) = 60$. - There is no bus that arrived at dispatch station $0$ earlier than bus $3$, so $t_{3,1} = \max([e_{3,1}]) = 30$. ``` arrival_time(0) ``` Bus $4$ needs $10$ seconds to travel one kilometer, and it is now planned to depart from the airport at second $0$. In this case, the table below lists the arrival times of each bus. The only changes in the regular buses' expected and actual arrival times are underlined. | $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$ | $40$ | | $55$ | $\underline{60}$ | | $1$ | | $10$ | | $30$ | $30$ | | $70$ | $70$ | | $130$ | $130$ | | $2$ | | $40$ | | $60$ | $60$ | | $100$ | $100$ | | $160$ | $180$ | | $3$ | | $0$ | | $30$ | $30$ | | $90$ | $90$ | | $180$ | $180$ | | $4$ | | $0$ | | $10$ | $10$ | | $30$ | $30$ | | $60$ | $60$ | From this, we can see that bus $4$ arrives at the hotel at second $60$. Therefore, the function should return $60$. ``` arrival_time(50) ``` Bus $4$ is now planned to depart from the airport at second $50$. In this case, compared to the initial table, the arrival times of the regular buses do not change. The table below lists the arrival times. | $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$ | $40$ | | $55$ | $55$ | | $1$ | | $10$ | | $30$ | $30$ | | $70$ | $70$ | | $130$ | $130$ | | $2$ | | $40$ | | $60$ | $60$ | | $100$ | $100$ | | $160$ | $180$ | | $3$ | | $0$ | | $30$ | $30$ | | $90$ | $90$ | | $180$ | $180$ | | $4$ | | $50$ | | $60$ | $60$ | | $80$ | $90$ | | $120$ | $130$ | Bus $4$ and the slower bus $2$ arrive at dispatch station $1$ at the same time, and then bus $4$ overtakes bus $2$. Next, while bus $4$ is traveling between dispatch stations $1$ and $2$, it is blocked by bus $3$, which makes it arrive at dispatch station $2$ at second $90$ instead of second $80$. After passing dispatch station $2$, bus $4$ is blocked by bus $1$ until they reach the hotel. Bus $4$ arrives at the hotel at second $130$. Therefore, the function should return $130$. Plot the time of each bus from departure at the airport to different distances as a polyline chart. In the figure, the $x$-axis represents the distance from the airport (in kilometers), and the $y$-axis represents time (in seconds). The vertical dashed lines mark the locations of the dispatch stations. The solid lines in different colors (labeled with bus numbers) represent the four regular buses. The black dotted line represents the spare bus. | `arrival_time(0)` | `arrival_time(50)` | |:-:|:-:| |  |  | --- **[Constraints]** * $1 \le L \le 10^9$ * $1 \le N \le 1\,000$ * $0 \le T[i] \le 10^{18}$（for each $i$ such that $0 \le i \lt N$） * $1 \le W[i] \le 10^9$（for each $i$ such that $0 \le i \lt N$） * $1 \le X \le 10^9$ * $2 \le M \le 1\,000$ * $0 = S[0] \lt S[1] \lt \cdots \lt S[M-1] = L$ * $1 \le Q \le 10^6$ * $0 \le Y \le 10^{18}$ --- **[Subtasks]** 1. (9 points) $N = 1, Q \le 1\,000$. 1. (10 points) $M = 2, Q \le 1\,000$. 1. (20 points) $N, M, Q \le 100$. 1. (26 points) $Q \le 5\,000$. 1. (35 points) No additional constraints. Translated by ChatGPT 5