ECOO '19 R1 P4 - Bus Route - DMOJ: Modern Online Judge

ECOO '19 R1 P4 - Bus Route

View as PDF

Submit solution

All submissions

Best submissions

Points: 12

Time limit: 13.0s

Memory limit: 512M

Problem types

Every morning, Lisa drives a public bus from one terminal stop to the other. Through months of careful observation, she has noticed that the order in which buses complete the route isn't necessarily the order in which they started. It is possible for the first bus to arrive at the first stop to not be the first bus to leave the last stop due to delays along the route. To leave work as early as possible, Lisa would like to figure out which bus will finish the route first on a given morning.

The route has $N$ $N$ bus stops (labelled $1$ $1$ to $N$ $N$ ) and $M$ $M$ daily passengers. Each passenger gets on a bus at some stop and gets off at a later stop. Each morning, the buses (labelled $1, 2, 3, \dots$ $1, 2, 3, \dots$ ) start at the first stop in $10$ $10$ -minute intervals, i.e., the $k+1$ $k + 1$ ^st bus starts $10$ $10$ minutes after the $k$ $k$ ^th bus.

A bus takes one minute to travel from one stop to the next. Each bus can carry $40$ $40$ people. Passengers at a bus stop board the buses in the order that they arrive at the stop. A bus will only stop at a bus stop if it is not full and there is a passenger waiting at the stop, or if someone on the bus wants to get off at the stop. If a bus stops, it first lets off any passengers that want to get off the bus, then picks up as many passengers that it can. Stopping delays a bus by one minute, regardless of how many people it picks up or drops off. If multiple buses arrive at a stop at the same time, they would stop in increasing order of their indices (i.e., the bus with the lowest index stops first).

Can you help Lisa by figuring out which bus she should drive to complete the route first?

Input Specification

The input will contain 10 datasets. Each dataset begins with two integers $N, M$ $N, M$ $(1 \le N, M \le 500\,000)$ $(1 \leq N, M \leq 500 000)$ . The next $M$ $M$ lines each contain two integers $S, F$ $S, F$ $(1 \le S < F \le N)$ $(1 \leq S < F \leq N)$ , which represent a passenger who wants to travel between stop $S$ $S$ and stop $F$ $F$ . If multiple people start at the same stop, buses pick them up in the order that they are listed.

For the first 4 datasets, $N, M \le 1\,000$ $N, M \leq 1 000$ .

Output Specification

For each dataset, output Bus #X, where X is the index of the bus that will be the first to reach the last stop. If two buses tie for first, output the one with the lower index.

Sample Input (Two Datasets Shown)

Copy

Sample Output

Copy

Bus #1
Bus #2

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

Comments

6

Kirito commented on April 3, 2019, 9:37 p.m.

To discourage hardcoding, the testcases are now shuffled between runs.

-2

Kevy3030 commented on April 27, 2020, 9:58 p.m.

When your team got 4/10 by guessing during the actual ECOO

-2

Joon7891 commented on June 23, 2019, 4:12 a.m. ← edit 3 →

:)