CSES - Nested Ranges Check | Kiểm tra đoạn bao chứa

Xem PDF

Điểm: 1400 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho \(n\) đoạn, nhiệm vụ của bạn là xác định xem với mỗi đoạn có chứa một số đoạn nào khác và có một số đoạn nào khác chứa nó hay không.

Đoạn \([a,b]\) chứa đoạn \([c,d]\) nếu \(a \le c\)\(d \le b\).

Input

  • Dòng đầu vào đầu tiên có một số nguyên \(n\): số lượng đoạn.
  • Sau này, có \(n\) dòng mô tả các đoạn. Mỗi dòng có hai số nguyên \(x\)\(y\): đoạn là \([x,y]\).
  • Bạn có thể giả định rằng không có đoạn nào xuất hiện nhiều hơn một lần trong đầu vào.

Output

  • Trước tiên, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) nếu nó chứa một số đoạn khác (1) hoặc không (0).
  • Sau đó, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) nếu có một số đoạn khác chứa nó (1) hoặc không (0).

Constraints

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le x < y \le 10^9\)

Example

Sample input

4
1 6
2 4
4 8
3 6

Sample output
1 0 0 0
0 1 0 1


Bình luận

Không có bình luận nào.