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
Your task is to implement the following procedures.
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
:
.
- 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
.
- Buses
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
)
Subtasks
- (9 points)
- (10 points)
- (20 points)
- (26 points)
- (35 points) No additional constraints.
Sample Grader
The sample grader reads the input in the following format:
- line
:
- line
:
- line
:
- line
:
- line
:
for question
The sample grader prints your answers in the following format:
- line
: the return value of
arrival_time
for question
Attachment Package
The sample grader along with sample test cases are available here.
Comments