Ichma-ich oraliqlar

$n$ ta oraliq $[x_i, y_i]$ berilgan. Har bir oraliq uchun ikkita savolga javob bering: u boshqa biror oraliqni o'z ichiga oladimi va uni boshqa biror oraliq o'z ichiga oladimi?

$[a, b]$ oraliq $[c, d]$ ni o'z ichiga oladi, agar $a \le c$ va $d \le b$ bo'lsa. Bir xil oraliqlar bir-birini o'z ichiga oladi; oraliq o'zini o'zi hisobga olinmaydi.

Birinchi qatorda $n$ ($1 \le n \le 2 \cdot 10^5$). Keyingi $n$ ta qatorda $x_i$ va $y_i$ ($1 \le x_i < y_i \le 10^9$).

Birinchi qatorda $n$ ta son: $i$-oraliq boshqasini o'z ichiga olsa 1, aks holda 0. Ikkinchi qatorda $n$ ta son: $i$-oraliqni boshqasi o'z ichiga olsa 1, aks holda 0.

Oraliqlarni chap uchi bo'yicha o'sish, chap uchlari teng bo'lsa o'ng uchi bo'yicha kamayish tartibida saralang. Shunda $i$ dan oldingi har bir oraliqning chap uchi $\le x_i$: $i$ ni biror oraliq o'z ichiga oladi $\iff$ oldingilarning eng katta o'ng uchi $\ge y_i$. Xuddi shunday, $i$ biror oraliqni o'z ichiga oladi $\iff$ keyingilarning eng kichik o'ng uchi $\le y_i$. Ikki o'tish (prefiks maksimum va suffiks minimum) — $O(n \log n)$.

Bir xil oraliqlarni alohida tekshiring: ulardan biri saralangan tartibda birinchi turadi, lekin u ham keyingisi ichida yotadi. Misolda $[1, 6]$ oraliq $[2, 4]$ va $[3, 6]$ ni o'z ichiga oladi.

Manba: CSES, 2168-masala.