Official Analysis (C++)

Warning!

The model solution in the editorial is actually wrong on a couple of test cases. For example, for the following input:

2
on 5 5
none 3 10

The solution outputs the following:

0 5
3 10

However, the actual answer is

0 5
5 10

This is because the starting range in the solution was initialized as (−∞-\infty, ∞\infty) when in reality it should be [0, ∞\infty).

Implementation

Time Complexity O(N)\mathcal{O}(N)

with open("traffic.in") as read:
	num_miles = int(read.readline())


	segment_type = []
	start = []
	end = []


	for m in range(num_miles):
		curr_type, s, e = read.readline().split()
		segment_type.append(curr_type)

Video Solution

By Jay Fu

Video Solution Code

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum