P7712 [Ynoi2077] hlcpq

On a plane, you are given $n$ horizontal line segments and $n$ vertical line segments. It is guaranteed that no two different segments lie on the same straight line. If two segments have an intersection point, then they are connected. If $a, b$ are connected and $b, c$ are connected, then $a, c$ are connected. A segment $a$ is critical if and only if there exist two other segments $b, c$ such that $b, c$ are connected, and after deleting $a$, $b, c$ are no longer connected.

The first line contains an integer $n$. The next $n$ lines: the $i$-th line contains two integers $l, r$ ($1 \le l < r \le n$), representing a horizontal segment with $l \le x \le r$ and $y=i$. The next $n$ lines: the $i$-th line contains two integers $d, u$ ($1 \le d < u \le n$), representing a vertical segment with $x = i$ and $d \le y \le u$.

Output two lines, each being a $01$ string of length $n$. The $i$-th character of the first line is $1$ if and only if the $i$-th horizontal segment is critical. The $i$-th character of the second line is $1$ if and only if the $i$-th vertical segment is critical.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078&nzhtl1477 Constraints: for $100\%$ of the testdata, $2 \le n \le 10^5$. Translated by ChatGPT 5