Water Taxi
Time limit1sMemory limit128 MB
Given pickup and drop-off points along a line for many passengers picked up by a boat starting at 0 that must end at M, compute the minimum travel distance covering everyone.
- Level
Medium6 of 10
- Topics
- Greedy, Prefix sum, Intervals
- Solved
- No attempts yet
Problem
A large river runs through Sanggeun's city, and every house is located along the river. The houses are numbered from 0 to M in order, and the distance between two neighboring houses is 1 kilometer.
Sanggeun lives at house 0 and carries people by boat. Today he must arrive at house M by evening, and he wants to take every passenger on the way to their destination.
There are N people who want to ride the boat today. For each person, the pickup position and destination are given. The boat is large enough to carry all N people at the same time.
After delivering every passenger to their destination, Sanggeun must reach house M. Find the minimum distance he has to travel.
Input
The first line contains N and M. N <= 300,000 and 3 <= M <= 10^9.
Each of the next N lines contains the position where one person gets on the boat and that person's destination. Every position is an integer between 0 and M, inclusive.
Output
Print the minimum distance Sanggeun must travel to deliver every passenger and arrive at house M.