Hợp Nhất Đoạn Chạm Biên

Buổi 75-76 — Stress Test sorting
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved