Hợp Nhất Đoạn Chạm Biên
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho $N$ đoạn đóng $[l_i, r_i]$ trên trục số ($l_i \le r_i$, có thể $l_i = r_i$). Hai đoạn giao nhau hoặc chạm nhau tại đầu mút (ví dụ $[1, 3]$ và $[3, 5]$) sẽ được hợp nhất thành một đoạn duy nhất. Hãy cho biết sau khi hợp nhất còn lại bao nhiêu đoạn rời nhau và tổng độ dài của chúng là bao nhiêu.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 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$).
Dữ liệu ra
- In ra hai số nguyên: số lượng đoạn sau khi hợp nhất và tổng độ dài $\sum (r - l)$.
Ví dụ
| Input | Output |
|---|---|
| 4 1 3 3 5 7 7 2 4 |
2 4 |
Giới hạn
- $1 \le N \le 10^5$, $-10^9 \le l_i \le r_i \le 10^9$
Community Discussion