Vệ tinh của chúng ta vừa phát hiện một nền văn minh trên một hành tinh xa xôi. Một bức ảnh có độ phân giải thấp chụp một vùng hình vuông trên hành tinh cho thấy nhiều dấu hiệu của sự sống văn minh. Các chuyên gia đã xác định \(n\) điểm quan tâm, đánh số từ \(0\) đến \(n-1\). Chúng ta muốn chụp các ảnh có độ phân giải cao chứa tất cả các điểm này.

Vùng ảnh được chia thành một lưới \(m \times m\) ô vuông đơn vị. Các hàng được đánh số từ \(0\) đến \(m-1\) từ trên xuống, các cột được đánh số từ \(0\) đến \(m-1\) từ trái sang phải. Ký hiệu \((s,t)\) chỉ ô ở hàng \(s\), cột \(t\). Điểm quan tâm thứ \(i\) nằm trong ô \((r_i,c_i)\). Một ô có thể chứa nhiều điểm quan tâm.

Vệ tinh di chuyển trên đường chéo chính của lưới, nối góc trên bên trái với góc dưới bên phải. Nó có thể chụp ảnh độ phân giải cao của một vùng thỏa mãn cả ba điều kiện:

• Vùng có hình vuông.
• Hai góc đối diện của hình vuông nằm trên đường chéo chính của lưới.
• Mỗi ô của lưới nằm hoàn toàn bên trong hoặc hoàn toàn bên ngoài vùng được chụp.

Vệ tinh được chụp nhiều nhất \(k\) bức ảnh. Sau đó, nó truyền dữ liệu của mọi ô đã chụp về căn cứ, kể cả ô không chứa điểm quan tâm. Dữ liệu của mỗi ô chỉ được truyền một lần, dù ô đó xuất hiện trong nhiều ảnh.

Hãy chọn nhiều nhất \(k\) vùng hình vuông sao cho mọi ô chứa điểm quan tâm đều được chụp ít nhất một lần, đồng thời số ô được chụp ít nhất một lần là nhỏ nhất. Bạn cần tìm số ô nhỏ nhất này.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong aliens.h:

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c);

Trong Java, cài đặt phương thức sau trong lớp aliens:

public long take_photos(int n, int m, int k, int[] r, int[] c)

Trong C, giao diện là:

long long take_photos(int n, int m, int k, int* r, int* c);

• n: số điểm quan tâm.
• m: số hàng và số cột của lưới.
• k: số ảnh tối đa được chụp.
• r, c: hai mảng độ dài \(n\); điểm thứ \(i\) nằm trong ô (r[i], c[i]).
• Hàm trả về số ô nhỏ nhất được chụp ít nhất một lần, đồng thời phủ tất cả các điểm quan tâm. Giá trị trả về là số nguyên \(64\) bit.

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "aliens.h" thay cho #include "aliens_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(1 \le n \le 100\,000\).
• \(1 \le m \le 1\,000\,000\).
• \(1 \le k \le n\).
• \(0 \le r_i,c_i < m\) với mọi \(0 \le i < n\).
• Các cặp \((r_i,c_i)\) không nhất thiết phân biệt.

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các giới hạn tọa độ và \(1 \le k \le n\) luôn áp dụng.

Ví dụ

Lời gọi thứ nhất:

take_photos(5, 7, 2, [0, 4, 4, 4, 4], [3, 4, 6, 5, 6])

Có \(5\) điểm quan tâm trên lưới \(7 \times 7\), nằm trong bốn ô khác nhau: \((0,3)\), \((4,4)\), \((4,5)\), \((4,6)\). Có thể chụp nhiều nhất \(2\) ảnh.

Một cách phủ tất cả các điểm là chụp vùng \(6 \times 6\) từ ô \((0,0)\) đến \((5,5)\) và vùng \(3 \times 3\) từ ô \((4,4)\) đến \((6,6)\). Hai vùng chồng nhau trên \(4\) ô, nên tổng cộng có \(36+9-4=41\) ô được chụp. Cách này chưa tối ưu.

Phương án tối ưu chụp vùng \(4 \times 4\) từ ô \((0,0)\) đến \((3,3)\) và vùng \(3 \times 3\) từ ô \((4,4)\) đến \((6,6)\). Hai vùng phủ \(16+9=25\) ô, nên hàm trả về \(25\). Chụp ô \((4,6)\) một lần là đủ dù ô đó chứa hai điểm quan tâm.

Lời gọi thứ hai:

take_photos(2, 6, 2, [1, 4], [4, 1])

Hai điểm quan tâm nằm đối xứng tại \((1,4)\) và \((4,1)\). Bất kỳ ảnh hợp lệ nào chứa một điểm cũng chứa điểm kia. Chỉ cần chụp một vùng \(4 \times 4\), gồm \(16\) ô, nên hàm trả về \(16\).

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n,m,k\). Dòng \(2+i\), với \(0 \le i < n\), chứa hai số \(r_i,c_i\). Chương trình in giá trị trả về của take_photos trên một dòng.

5 7 2
0 3
4 4
4 6
4 5
4 6

25

2 6 2
1 4
4 1

16

Nguồn

IOI 2016, ngày thi thứ hai, bài Aliens. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.