Kiểm tra Đoạn Lồng nhau

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho $n$ đoạn thẳng, đoạn thứ $i$ có tọa độ $[x_{i}, y_{i}]$ . Đoạn $[a, b]$ được gọi là chứa đoạn $[c, d]$ nếu $a \leq c$ và $d \leq b$ .

Với mỗi đoạn thẳng, hãy xác định:

Dòng đầu: số nguyên $n$ — số lượng đoạn thẳng.
$n$ dòng tiếp theo, dòng thứ $i$ : hai số nguyên $x_{i}$ và $y_{i}$ ( $x_{i} < y_{i}$ ).

Dòng 1: $n$ số nguyên $c_{1}, c_{2}, \dots, c_{n}$ , trong đó $c_{i} = 1$ nếu đoạn $i$ chứa ít nhất một đoạn khác, ngược lại $c_{i} = 0$ .
Dòng 2: $n$ số nguyên $d_{1}, d_{2}, \dots, d_{n}$ , trong đó $d_{i} = 1$ nếu đoạn $i$ được chứa bởi ít nhất một đoạn khác, ngược lại $d_{i} = 0$ .

Input	Output	Giải thích
4 1 6 2 4 4 8 3 6	1 0 0 1 0 1 0 1	Đoạn $[1, 6]$ chứa $[2, 4]$ và $[3, 6]$ . Đoạn $[3, 6]$ được chứa bởi $[1, 6]$ . Đoạn $[2, 4]$ được chứa bởi $[1, 6]$ .
3 1 10 2 5 3 4	1 1 0 0 1 1	$[1, 10]$ chứa cả hai đoạn kia. $[2, 5]$ chứa $[3, 4]$ và được chứa bởi $[1, 10]$ .

Bình luận

Không có bình luận tại thời điểm này.