P1695 [USACO19FEB] Measuring Traffic B

Recently, the highway next to Farmer John’s farm has seen a noticeable increase in traffic, or at least it seems so to Farmer John. To confirm this, he plans to use a set of sensors to measure the traffic flow on the highway, where each sensor is used to measure the traffic flow value on a small section of road. Unfortunately, one day while passing the barn, Farmer John tripped, and the box containing the sensors fell into a huge milk tank. After that, they no longer worked properly. Instead of producing an exact traffic flow reading as before, each sensor can now only output a range of possible results. For example, a sensor might output the range $[7,13]$, meaning that the traffic flow on this section of road is at least $7$ and at most $13$. The highway segment passing the farm is $N$ miles long, and cars travel only in one direction, from mile $1$ to mile $N$. Farmer John wants to install $N$ sensors—each monitoring a $1$-mile section of the highway. On some sections, there are on-ramps that allow cars to enter the highway; on every such section, Farmer John will place the sensor on the on-ramp to measure the (approximate) incoming traffic flow. On some sections, there are off-ramps that allow cars to leave the highway; on every such section, Farmer John will place the sensor on the off-ramp. Each section contains at most one ramp. If a section has neither an on-ramp nor an off-ramp, Farmer John will place the sensor on the main road of the highway. Given the readings from Farmer John’s $N$ sensors, determine the most accurate possible ranges for the traffic flow before mile $1$ and after mile $N$. These ranges should be consistent with the readings of all $N$ sensors.

The first line of input contains $N$ ($1\le N\le 100$). The remaining $N$ lines each describe a $1$-mile section, in order from mile $1$ to mile $N$. Each line contains a string: `on` (if this section has an on-ramp), `off` (if this section has an off-ramp), or `none` (if this section has no ramp), followed by two integers in the range $0\ldots 1000$, giving the lower and upper bounds of the sensor’s reading for this section. If the section contains a ramp, the sensor reading comes from the ramp; otherwise, it comes from the main road. At least one highway section description will be `none`.

Output two integers on the first line: the most accurate possible range of traffic flow before mile $1$. Output two integers on the second line: the most accurate possible range of traffic flow after mile $N$. The input guarantees that a solution satisfying the requirements exists.

### Sample Explanation 1 In this example, the readings for sections $2$ and $3$ together tell us that the traffic flow through these two sections is some value in the range $[11,14]$, because only this range is consistent with both readings $[10,14]$ and $[11,15]$. At mile $1$, exactly $1$ unit of traffic enters through the on-ramp, so before mile $1$, the traffic flow must be within the range $[10,13]$. At mile $4$, between $2$ and $3$ units of traffic leave through the off-ramp, so the possible traffic flow range after this section is $[8,12]$. Translated by ChatGPT 5