Quy hoạch
Xem dạng PDFPhòng quy hoạch đô thị sử dụng hệ trục tọa độ ~Oxy~ để mô hình hóa phần đất quản lý. Hiện nay, phòng nhận được ~n~ tờ trình, tờ trình thứ ~i~ (~1 \le i \le n~) xin cấp một khu đất hình chữ nhật có các cạnh song song với các trục tọa độ, xác định bởi tọa độ góc trái dưới ~(x_1, y_1)~ và góc phải trên ~(x_2, y_2)~. Các khu đất có thể chồng lấn nhau tùy ý.
Một điểm trên mặt đất được gọi là điểm tranh chấp mức ~K~ nếu nó nằm trong ít nhất ~K~ khu đất được xin cấp phép. Lưu ý rằng điểm nằm trên biên của một khu đất cũng được tính là nằm trong khu đất đó.
Hãy tính tổng diện tích phần mặt đất gồm các điểm tranh chấp mức ~K~.
Input BAI2.INP
- Dòng đầu chứa hai số nguyên ~n~, ~K~ (~1 \le n \le 10^5~; ~1 \le K \le 10~) lần lượt là số lượng tờ trình và mức độ tranh chấp ~K~.
- Tiếp theo là ~n~ dòng, mỗi dòng mô tả một khu đất được xin cấp gồm bốn số nguyên ~x_1, y_1, x_2, y_2~ (~0 \le x_1 < x_2 \le 10^9~; ~0 \le y_1 < y_2 \le 10^9~).
Output BAI2.OUT
In ra một số nguyên duy nhất là diện tích cần tìm.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 25% | ~n \le 300~ và mọi tọa độ không vượt quá 300 |
| 2 | 20% | ~K = 1~ |
| 3 | 20% | ~n \le 3000~ |
| 4 | 35% | Không có ràng buộc bổ sung |
Sample Input 1
3 2
0 0 3 2
1 1 4 3
2 0 5 4
Sample Output 1
6
Notes
Ba khu đất lần lượt là:
- Khu 1: ~(0, 0) \to (3, 2)~;
- Khu 2: ~(1, 1) \to (4, 3)~;
- Khu 3: ~(2, 0) \to (5, 4)~.
[Minh họa ba khu đất trong ví dụ]
Phần đất bị đúng hai khu phủ gồm ba mảnh có diện tích 1, 1, 3; phần bị cả ba khu phủ có diện tích 1 và cũng được tính. Tổng diện tích các điểm nằm trong ít nhất hai khu bằng 6.