Đếm Đoạn Thẳng Bao Phủ

Buổi 31 — Policy-Based DS
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho $N$ đoạn thẳng trên trục số $[L_i, R_i]$ ($1 \le i \le N$). Với mỗi đoạn thẳng $i$, hãy đếm xem có bao nhiêu đoạn thẳng $j \ne i$ nằm hoàn toàn bên trong đoạn $i$ (tức $L_i \le L_j$ và $R_j \le R_i$).

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($1 \le N \le 2 \cdot 10^5$).
  • $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L_i, R_i$ ($-10^9 \le L_i \le R_i \le 10^9$). Đảm bảo không có hai đoạn thẳng nào trùng hệt cả hai đầu mút.
Dữ liệu ra
  • In ra $N$ số nguyên cách nhau bởi dấu cách, số thứ $i$ là số đoạn nằm trong đoạn $i$.
Ví dụ
Input Output
4
1 5
2 4
3 3
1 3
3 1 0 1
Giới hạn
  • $1 \le N \le 2 \cdot 10^5$
Draft saved