Đếm Đ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 đếm:

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}$ là số đoạn khác mà đoạn $i$ chứa.
Dòng 2: $n$ số nguyên $d_{1}, d_{2}, \dots, d_{n}$ , trong đó $d_{i}$ là số đoạn khác mà đoạn $i$ được chứa bởi.

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

Bình luận

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