#5421. Đếm các khoảng lồng nhau (Mã bài: NRC)

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho n khoảng [a_i, b_i] . Nhiệm vụ của bạn là, với mỗi khoảng, hãy đếm xem có bao nhiêu khoảng khác chứa nó và có bao nhiêu khoảng khác bị nó chứa. Một khoảng [a_j, b_j] chứa khoảng [a_i, b_i] nếu a_j \le a_i b_i \le b_j .

Dữ liệu:

  • Dòng đầu tiên là số nguyên n .
  • n dòng tiếp theo, mỗi dòng chứa hai số nguyên a_i b_i mô tả một khoảng.

Kết quả:

  • In ra hai dòng.
  • Dòng đầu tiên gồm n số: số khoảng chứa khoảng thứ i (theo thứ tự nhập).
  • Dòng thứ hai gồm n số: số khoảng bị khoảng thứ i chứa.

Ví dụ:

Dữ liệu:

5
1 6
2 4
4 8
3 6
7 8

Kết quả:

0 1 1 1 1 
2 0 0 0 0 

Giới hạn:

  • 1 \le n \le 2 \cdot 10^5
  • 1 \le a_i \le b_i \le 10^9