CSES - Nested Ranges Count | Đếm đoạn bao chứa

Xem PDF

Điểm: 1600 (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à đếm xem với mỗi đoạn chứa bao nhiêu đoạn khác và có bao nhiêu đoạn khác chứa nó.

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

Input

  • Dòng đầu vào đầu tiên có một số nguyên \(n\) \((1 \leq n \leq 2 \times 10^{5})\) - 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\) \((1 \leq x < y \leq 10^{9})\) - đ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) có bao nhiêu đoạn khác mà nó chứa.
  • Sau đó, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) có bao nhiêu đoạn khác chứa nó.

Example

Test 1

Input
4
1 6
2 4
4 8
3 6
Output
2 0 0 0
0 1 0 1

Bình luận

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