AtCoder ABC355 D - Các đoạn giao nhau
Xem PDF
Điểm:
1400
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Cho \(N\) đoạn đóng \([l_i,r_i]\) trên trục số. Hãy đếm số cặp \((i,j)\) với \(1\le i<j\le N\) mà hai đoạn có ít nhất một điểm chung. Hai đoạn chỉ chạm nhau tại đầu mút cũng được tính.
Dữ liệu vào
- Dòng đầu chứa \(N\).
- \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(l_i,r_i\).
Dữ liệu ra
In ra số cặp cần tìm.
Ràng buộc
- \(2\le N\le5\cdot10^5\).
- \(0\le l_i<r_i\le10^9\).
- Mọi giá trị đầu vào đều là số nguyên.
Ví dụ
Ví dụ 1
Input
3
1 5
7 8
3 7Output
2Giải thích
Hai cặp giao nhau là \((1,3)\) và \((2,3)\); cặp thứ hai gặp nhau tại điểm \(7\).
Ví dụ 2
Input
3
3 4
2 5
1 6Output
3Giải thích
Mọi cặp đều giao nhau.
Ví dụ 3
Input
2
1 2
3 4Output
0Giải thích
Hai đoạn không có điểm chung.
Bình luận