Problem A
Pixelated
An LCD panel is composed of a grid of pixels, spaced $1$ alu (“arbitrary length unit”) apart both horizontally and vertically. Wires run along each row and each column, intersecting at the pixels. Wires are numbered beginning with $1$ and proceeding up to a panel-dependent maximum. The vertical wire numbered $1$ lies along the left edge of the panel, and the horizontal wire numbered $1$ lies along the bottom edge of the panel.
A pixel will activate, turning dark, when a current is present along both the vertical and horizontal wire passing through that pixel.
For a period of time, we will send pulses of current down selected wires. The current flows down the wires at a speed of one alu per atu (“arbitrary time unit”). The pulses themselves have a length measured in atus. A pixel activates when current is passing through both intersecting wires at the same time. If the leading edge of a pulse on one wire reaches the intersection at the exact same time that the trailing edge of a pulse on the other wire leaves that intersection, the pixel is not activated.
All pulses in vertical wires start from the bottom of the grid. All pulses in horizontal wires start from the left of the grid. At most one pulse will travel along any one wire.
Given the schedule of pulses to be sent through the wires, determine how many pixels will have been activated by the time all pulses have exited the top and right of the grid.
Input
The first line contains $n$, the number of current pulses, with $1\le n\le 200\, 000$.
Following this are $n$ lines, each describing a single pulse. Each such line contains four elements, separated from one another by a single space:
-
A single character that is either ‘h’ or ‘v’, indicating the horizontal/vertical direction of the pulse.
-
An integer $t$, $1\le t\le 200\, 000$, denoting the starting time of the pulse. The starting time is considered to be the moment when the leading edge of a vertical [horizontal] pulse crosses horizontal [vertical] wire #$1$.
-
An integer $m$, $1\le m\le 200\, 000$, denoting the length of the pulse.
-
An integer $a$, $1\le a\le 100\, 000$, denoting the wire number (horizontal or vertical) along which the pulse travels.
Output
Print on a single line the number of pixels that will have activated by the time the last pulse of current has left the grid.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 h 1 4 1 v 2 4 2 h 10 2 2 v 11 2 3 |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 h 1 10 1 h 5 10 2 v 1 10 1 v 5 10 3 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 v 1 3 1 v 1 15 2 h 4 5 1 h 5 5 2 h 6 5 3 h 7 5 4 h 8 5 5 |
5 |
