PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
EXPLANATION:
This is a straight forward question.
The train can travel both ways and it takes the same time in both directions. Hence, for two stations a and b, we can assign a as min(a,b) and b as max(a,b).
The naive approach is as follows:
-
For query type 0, add all the travel times from a to b and the waiting times in between. Note that for adjacent stations there is no waiting time and to travel from a to a, it takes no time.
-
For query type 1, add all the travel times from a to b. Find the minimum waiting time among the stations between a and b. Multiply the minimum waiting time by the number of intermediate stations and add it to the total time.
This approach takes O(n) for each query.
We can optimize this by using prefix sum arrays.
For query type 0, we can create prefix sum arrays for both travel times and waiting times at the beginning. This takes O(n) at the beginning. This is done only once. But for each query, we can find the answer in O(1).
For query type 1, we can create prefix sum array for travel time and use any range minimum query(RMQ) algorithms to find the minimum waiting time. The complexity of this depends on the algorithm chosen for RMQ.
AUTHOR’S AND TESTER’S SOLUTIONS:
The first two solutions use naive apporach. The last solution uses prefix sum arrays.