Bus Stops

If you take the TTC, you'll know that often buses can only carry a certain number of people (call this C).
Sometimes, you get left stranded at the bus stop when the bus is full.
If you're lazy, you'll just wait for the next bus. But sometimes, it might just be better to walk to another stop beforehand.

In our scenario, there is only one bus, and so some people might be required to walk.
Let's suppose you know in advance all N of the passengers and where they want to get on and off.
Now, you want to create a plan so that each passenger spends the least amount of time in transit to reach his/her destination.
All passengers are treated equally - we just want to minimize the total time for all passengers.

The bus starts at bus stop #1 and goes "rightward", going to bus stop 2, then 3, etc.
The bus stops, numbered 1,2,3 ... B, are located along a perfectly straight street.
It takes 5 minutes to walk from one bus stop to the next, and 1 minute to do the same by bus.


Three integers, passengers (N) ≤ 1,000,000, stops (B) ≤ 1,000,000, capacity (C) ≤ N
N pairs of integers, representing the start and end stops of a passenger.
Passengers get to their starting stops instantly.
Assume that they get to their required bus stop right on time: they won't have to wait for the bus.
All numbers will be positive integers.


The total time taken for all the passengers to get to work, assuming an optimal schedule.

Sample Input

3 5 2
1 5
2 5
3 4

Sample Output


The bus only holds 2 people, so the third guy has to walk. (No passenger is favored over another)
Passenger 1: takes the bus (4 minutes)
Passenger 2: takes the bus (3 minutes)
Passenger 3: walks from 3-4 (5 minutes)

Sample Input

5 8 1
1 3
2 4
2 5
6 7
7 8

Sample Output


In this case, the bus is more like a taxi.
Passenger 1: Just takes the bus (2 minutes)
Passenger 2: walks to stop 3 first (5 minutes) and then takes the bus to 4 (1 minute)
Passenger 3: walks to stop 4 first (10 minutes) and then takes the bus to 5 (1 minute)
Passengers 4/5: just take the bus (1+1 minutes)

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 02, 2008
Author: hansonw1

Problem Types: [Show]

Languages Allowed:

Comments (Search)

I think the time should be increased somewhat to account for Java... I did this in C++, but my identical Java code TLEs on the last case.

Sorry, I was experimenting with different VMs. The 'cacao' VM uses less memory, because it performs just-in-time compilation (I think), but it appears that it is also producing slower code. So I ditched that. Java programs should be somewhat faster now. (I can't seem to measure the memory usage anyway right now --- it is always reporting 2.6 M for some reason.)

Our current policy is basically to ignore the fact that Java exists at all, mostly because it's a lot harder to grade Java programs accurately than it is to grade C/C++/Pascal ones. This may change if they ever start allowing Java at the IOI, but according to kolstad it's not likely to happen soon, as it gets proposed (and subsequently rejected) every year.

(NB: kolstad also implied that the only reason why Java is allowed in USACO is that it's unreasonably popular among Americans. He's probably also one of very few people in the world with enough technical expertise to grade it properly.)

i dont get the senerio

Was this problem clear enough? Did you guys understand it?
Or was it just too hard? (It's not too bad, the solution is very simple)