Bedao OI Contest 6 - Tranh giáng sinh
View as PDF
Chuẩn bị đến dịp lễ Giáng sinh, Hưng muốn ngôi nhà thêm đẹp mắt và đặc biệt. Cậu đã quyết định mua một số bức tranh dán tường để trang trí ngôi nhà của mình. Bề mặt của bức tường có thể được xem là một lưới ô vuông gồm ~N~ hàng và ~N~ cột.
Các dòng được đánh số từ ~1~ đến ~N~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~N~ từ trái sang phải. Ô nằm trên dòng ~i~ và cột ~j~ được gọi là ô (~i, j~).
Hưng đã mua và dán ~M~ bức tranh dán lên tường, bức tranh thứ ~i~ được miêu tả bởi ~4~ số nguyên ~x_1, x_2, y_1, y_2~ cho biết bức tranh bao phủ toàn bộ các ô của lưới ô vuông con có góc trái trên là ô (~x_1, y_1~) và góc phải dưới là ô (~x_2, y_2~).
Sau khi dán hết các bức tranh, Hưng nhận thấy rằng vị trí các bức tranh rất bừa bộn. Để làm giảm sự bừa bộn, Hưng muốn tìm cách bỏ đi đúng hai bức tranh sao cho số ô không được phủ bởi bất cứ bức tranh nào là lớn nhất có thể.
Vì đang tập trung ôn VOI nên Hưng khá bận, bạn hãy giúp Hưng làm điều này nhé.
Input
Dữ liệu vào từ file văn bản christmas.inp.
Dòng đầu tiên gồm ~2~ số nguyên ~M~ và ~N~ (~3 \le M \le 200000~, ~1 \le N \le 5000~) — là số bức tranh và kích thước của lưới ô vuông.
~M~ dòng tiếp theo, dòng thứ ~i~ gồm ~4~ số nguyên ~x_1, x_2, y_1, y_2~ (~1 \le x_1 \le x_2 \le N~, ~1 \le y_1 \le y_2 \le N~) – mô tả bức tranh thứ ~i~.
Output
In ra file văn bản christmas.out một số duy nhất là số ô không bị phủ lớn nhất có thể sau khi bỏ đi ~2~ bức tranh.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20~ | ~M, N \le 80~ |
| 2 | ~20~ | ~M \le 2000~ |
| 3 | ~20~ | ~M \le 20000, N \le 100~ |
| 4 | ~40~ | Không có ràng buộc gì thêm |
Sample Input 1
3 5
1 5 1 5
1 4 2 5
2 3 3 4
Sample Output 1
21
Sample Input 2
4 9
1 5 1 4
3 7 2 5
4 8 2 4
4 8 1 6
Sample Output 2
58
Notes
Trong test ví dụ đầu tiên, sau khi chọn bỏ đi bức tranh thứ nhất và thứ hai thì số ô không bị phủ bởi bất kỳ bức tranh nào là ~21~.
Trong test ví dụ thứ hai, sau khi chọn bỏ đi bức tranh thứ nhất và thứ ~4~ thì số ô không bị phủ là ~58~.
Comments
.
.