Nested Ranges Check

题目描述

给定 n 个区间，你的任务是判断对于每个区间它是否包含某个其他区间以及是否被某个其他区间包含。 区间 $[a,b]$ 包含区间 $[c,d]$ 当且仅当 $a \le c$ 且 $d \le b$。

输入格式

第一行输入包含一个整数 n：区间的数量。 接下来有 n 行描述这些区间。每行包含两个整数 x 和 y：区间为 $[x,y]$。 你可以假设输入中不会出现重复的区间。

输出格式

首先输出一行，按输入顺序对于每个区间输出它是否包含某个其他区间（包含则为 1，否则为 0）。 然后输出一行，按输入顺序对于每个区间输出是否被某个其他区间包含（被包含则为 1，否则为 0）。

4
1 6
2 4
4 8
3 6

1 0 0 0
0 1 0 1

提示

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

标签: CSES2168|排序和搜索

来源

CSES2168|排序和搜索