链接: https://cses.fi/problemset/task/2168

板块: Sorting and Searching

时限: 1.00 s ｜ 内存: 512 MB

题目描述

给定 $n$ 个区间，你的任务是判断每个区间是否包含某个其他区间，以及是否被某个其他区间包含。

当 $a \le c$ 且 $d \le b$ 时，区间 $[a,b]$ 包含区间 $[c,d]$。

输入

第一行包含一个整数 $n$：区间数量。

之后有 $n$ 行描述区间。每行包含两个整数 $x$ 和 $y$：该区间为 $[x,y]$。

你可以假定输入中每个区间最多出现一次。

输出

先输出一行，按输入顺序描述每个区间是否包含某个其他区间（$1$ 表示是，$0$ 表示否）。

再输出一行，按输入顺序描述每个区间是否被某个其他区间包含（$1$ 表示是，$0$ 表示否）。

数据范围

$1 \le n \le 2 \cdot 10^5$ $1 \le x < y \le 10^9$

样例输入

4
1 6
2 4
4 8
3 6

样例输出

1 0 0 0
0 1 0 1