P1382 Buildings

There are $n$ buildings on the horizon (the $x$ axis), and each building is represented as a rectangle. The $i$-th rectangle is represented by three integers $h_i, l_i, r_i$: its bottom-left corner is at $(l_i, 0)$ and its top-right corner is at $(r_i, h_i)$. The horizon has height $0$. Subject to minimizing the skyline polyline length (i.e., without redundant points), output the skyline from left to right.

The first line contains an integer $n$, the number of rectangles. Each of the following $n$ lines contains $3$ integers $h_i, l_i, r_i$ describing the $i$-th rectangle.

The first line contains an integer $m$, the number of nodes. Each of the following $m$ lines contains one coordinate, representing a node on the skyline. Traverse the skyline from left to right and output the nodes in order. Note: The $y$-coordinates of the first and the last node are both $0$.

Sample 2 as shown:   Constraints: For $30\%$ of the testdata, $n \le 100$. For another $30\%$ of the testdata, $1 \le h_i, l_i, r_i \le 1000$. For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le h_i \le 10^9$, $-10^9 \le l_i < r_i \le 10^9$. Translated by ChatGPT 5