29749번 - Overtaking 서브태스크다국어언어 제한함수 구현

문제

There is a one-lane, one-way road from Budapest Airport to Hotel Forrás. The road is $L$ kilometres long.

Over the IOI 2023 event, $N+1$ transfer buses traverse this road. Buses are numbered from 0ドル$ to $N$. Bus $i$ (0ドル \le i \lt N$) is scheduled to leave the airport at the $T[i]$-th second of the event, and can travel 1ドル$ kilometre in $W[i]$ seconds. Bus $N$ is a reserve bus that can travel 1ドル$ kilometre in $X$ seconds. The time $Y$ when it will leave the airport has not yet been decided.

Overtaking is not allowed on the road in general, but the buses are allowed to overtake each other at sorting stations. There are $M$ ($M \gt 1$) sorting stations, numbered from 0ドル$ to $M - 1,ドル on different positions on the road. Sorting station $j$ (0ドル \le j \lt M$) is located $S[j]$ kilometres from the airport along the road. The sorting stations are sorted in increasing distance from the airport, that is, $S[j] \lt S[j+1]$ for each 0ドル \le j \le M - 2$. The first sorting station is the airport and the last one is the hotel, that is, $S[0] = 0$ and $S[M-1] = L$.

Each bus travels at maximum speed unless it catches up to a slower bus travelling ahead of it on the road, in which case they get bunched and forced to travel at the speed of the slower bus, until they reach the next sorting station. There, the faster buses will overtake the slower buses.

Formally, for each $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 sorting station $j$ is defined as follows. Let $t_{i,0} = T[i]$ for each 0ドル \le i \lt N,ドル and let $t_{N,0} = Y$. For each $j$ such that 0ドル \lt j \lt M$:

• Define the expected time of arrival (in seconds) of bus $i$ at sorting station $j,ドル denoted by $e_{i,j},ドル as the time when bus $i$ would arrive at sorting station $j$ if it was travelling at full speed from the time it arrived at sorting station $j-1$. That is, le
  • $e_{i,j} = t_{i,j-1} + W[i] \cdot (S[j]-S[j-1])$ for each 0ドル \le i \lt N,ドル and
  • $e_{N,j} = t_{N,j-1} + X \cdot (S[j]-S[j-1])$.
• Bus $i$ arrives at sorting station $j$ at the *maximum* of the expected times of arrivals of bus $i$ and of every other bus that arrived at station $j-1$ earlier than bus $i$. Formally, let $t_{i,j}$ be the maximum of $e_{i,j}$ and every $e_{k,j}$ for which 0ドル \le k \le N$ and $t_{k,j-1} \lt t_{i,j-1}$.

The IOI organizers want to schedule the reserve bus (bus $N$). Your task is to answer $Q$ questions of the organizers, which are of the following form: given the time $Y$ (in seconds) when the reserve bus is supposed to leave the airport, at what time would it arrive at the hotel?

구현

Your task is to implement the following procedures.

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 non-reserve buses.
• $T$: an array of length $N$ describing the times at which non-reserve buses are scheduled to leave from the airport.
• $W$: an array of length $N$ describing the maximum speeds of non-reserve buses.
• $X$: the time it takes for the reserve bus to travel 1ドル$ kilometre.
• $M$: the number of sorting stations.
• $S$: an array of length $M$ describing the distances of the sorting stations from the airport.
• This procedure is called exactly once for each test case, before any calls to arrival_time.

int64 arrival_time(int64 Y)

• $Y$: the time at which the reserve bus (bus $N$) is supposed to leave from the airport.
• This procedure should return the time at which the reserve bus would arrive at the hotel.
• This procedure is called exactly $Q$ times.

예제

Consider the following sequence of calls:

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

Ignoring bus 4ドル$ (that has not yet been scheduled), the following table shows the expected and actual times of arrivals for non-reserve buses at each sorting station:

The times of arrivals at station 0ドル$ are the times at which buses are scheduled to leave the airport. That is, $t_{i,0} = T[i]$ for 0ドル \le i \le 3$.

The expected and actual times of arrivals at sorting station 1ドル$ are computed as follows:

• The expected times of arrivals at 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$.
• The times of arrivals at station 1ドル$:
  • Buses 1ドル$ and 3ドル$ arrive at station 0ドル$ earlier than bus 0ドル,ドル so $t_{0,1} = \max([e_{0,1},e_{1,1},e_{3,1}]) = 30$.
  • Bus 3ドル$ arrives at station 0ドル$ earlier than bus 1ドル,ドル so $t_{1,1} = \max([e_{1,1},e_{3,1}]) = 30$.
  • Bus 0ドル,ドル bus 1ドル$ and bus 3ドル$ arrive at sorting station 0ドル$ earlier than bus 2ドル,ドル so $t_{2,1} = \max([e_{0,1},e_{1,1},e_{2,1},e_{3,1}]) = 60$.
  • No bus arrives at station 0ドル$ earlier than bus 3ドル,ドル so $t_{3,1} = \max([e_{3,1}]) = 30$.

arrival_time(0)

Bus 4ドル$ takes 10ドル$ seconds to travel 1ドル$ kilometre and is now scheduled to leave the airport at the 0ドル$-th second. In this case, the following table shows the times of arrivals for each bus. The only change regarding the expected and actual arrival times of the non-reserve buses is underlined.

We see that bus 4ドル$ arrives at the hotel at the 60ドル$-th second. Thus, the procedure should return 60ドル$.

arrival_time(50)

Bus 4ドル$ is now scheduled to leave the airport at the 50ドル$-th second. In this case, there are no changes in the times of arrivals for the non-reserve buses compared to the initial table. The times of arrivals are shown in the following table.

Bus 4ドル$ overtakes the slower bus 2ドル$ at sorting station 1ドル$ as they arrive at the same time. Next, bus 4ドル$ gets bunched with bus 3ドル$ between station 1ドル$ and station 2ドル,ドル making bus 4ドル$ arrive at station 2ドル$ at the 90ドル$-th second instead of the 80ドル$-th. After leaving station 2ドル,ドル bus 4ドル$ gets bunched with bus 1ドル$ up until they arrive at the hotel. Bus 4ドル$ arrives at the hotel at the 130ドル$-th second. Thus, the procedure should return 130ドル$.

We can plot the time it takes for each bus to arrive at each distance from the airport. The x-axis of the plot represents the distance from the airport (in kilometres) and the y-axis of the plot represents the time (in seconds). Vertical dashed lines mark the positions of the sorting stations. Different solid lines (accompanied by the bus indices) represent the four non-reserve buses. The dotted black line represents the reserve bus.

입력

출력

제한

• 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}$

서브태스크

힌트

샘플 그레이더

The sample grader reads the 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$): $Y$ for question $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 question $k$

첨부

• overtaking.zip