## IOI '23 P5 - Overtaking

View as PDF

Points: 25 (partial)
Time limit: 2.5s
Memory limit: 1G

Problem type
Allowed languages
C++

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

Over the IOI 2023 event, transfer buses traverse this road. Buses are numbered from to . Bus is scheduled to leave the airport at the -th second of the event, and can travel kilometre in seconds. Bus is a reserve bus that can travel kilometre in seconds. The time 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 sorting stations, numbered from to , on different positions on the road. Sorting station is located kilometres from the airport along the road. The sorting stations are sorted in increasing distance from the airport, that is, for each . The first sorting station is the airport and the last one is the hotel, that is, and .

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 and such that and , the time (in seconds) when bus arrives at sorting station is defined as follows. Let for each , and let . For each such that :

• Define the expected time of arrival (in seconds) of bus at sorting station , denoted by , as the time when bus would arrive at sorting station if it was travelling at full speed from the time it arrived at sorting station . That is, let
• for each , and
• .
• Bus arrives at sorting station at the maximum of the expected times of arrivals of bus and of every other bus that arrived at station earlier than bus . Formally, let be the maximum of and every for which and .

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

#### Implementation Details

void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)

• : the length of the road.
• : the number of non-reserve buses.
• : an array of length describing the times at which non-reserve buses are scheduled to leave from the airport.
• : an array of length describing the maximum speeds of non-reserve buses.
• : the time it takes for the reserve bus to travel kilometre.
• : the number of sorting stations.
• : an array of length 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.
long long arrival_time(long long Y)

• : the time at which the reserve bus (bus ) 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 times.

#### Example

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 (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 are the times at which buses are scheduled to leave the airport. That is, for .

The expected and actual times of arrivals at sorting station are computed as follows:

• The expected times of arrivals at station :
• Bus : .
• Bus : .
• Bus : .
• Bus : .
• The times of arrivals at station :
• Buses and arrive at station earlier than bus , so .
• Bus arrives at station earlier than bus , so .
• Bus , bus and bus arrive at sorting station earlier than bus , so .
• No bus arrives at station earlier than bus , so .
arrival_time(0)


Bus takes seconds to travel kilometre and is now scheduled to leave the airport at the -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 arrives at the hotel at the -th second. Thus, the procedure should return .

arrival_time(50)


Bus is now scheduled to leave the airport at the -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 overtakes the slower bus at sorting station as they arrive at the same time. Next, bus gets bunched with bus between station and station , making bus arrive at station at the -th second instead of the -th. After leaving station , bus gets bunched with bus up until they arrive at the hotel. Bus arrives at the hotel at the -th second. Thus, the procedure should return .

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.

arrival_time(0) arrival_time(50)

#### Constraints

• (for each such that )
• (for each such that )

1. (9 points)
2. (10 points)
3. (20 points)
4. (26 points)
5. (35 points) No additional constraints.

• line :
• line :
• line :
• line :
• line : for question

• line : the return value of arrival_time for question