Nested ranges

You are given $n$ ranges $[x_i, y_i]$. For every range answer two questions: does it contain some other range, and is it contained in some other range?

Range $[a, b]$ contains $[c, d]$ if $a \le c$ and $d \le b$. Identical ranges contain each other; a range does not count itself.

The first line contains $n$ ($1 \le n \le 2 \cdot 10^5$). The next $n$ lines contain $x_i$ and $y_i$ ($1 \le x_i < y_i \le 10^9$).

The first line contains $n$ numbers: 1 if range $i$ contains another range, otherwise 0. The second line contains $n$ numbers: 1 if range $i$ is contained in another range, otherwise 0.

Sort the ranges by left end in increasing order and, for equal left ends, by right end in decreasing order. Then every range before $i$ has left end $\le x_i$: range $i$ is contained in another $\iff$ the largest right end among the previous ones is $\ge y_i$. Similarly, range $i$ contains another $\iff$ the smallest right end among the following ones is $\le y_i$. Two passes (prefix maximum and suffix minimum) — $O(n \log n)$.

Handle identical ranges separately: one of them comes first in sorted order, yet it also lies inside the next one. In the example $[1, 6]$ contains $[2, 4]$ and $[3, 6]$.

Source: CSES, problem 2168.