Vào đầu thế kỷ 19, nhà cai trị Hoseyngulu Khan Sardar ra lệnh xây dựng một cung điện trên một cao nguyên nhìn xuống dòng sông rất đẹp. Cao nguyên này được mô hình hóa như một lưới ô vuông \(n \times m\). Các hàng của lưới được đánh số từ \(0\) đến \(n-1\) và các cột được đánh số từ \(0\) đến \(m-1\). Gọi ô tại hàng \(i\) và cột \(j\) (\(0 \leq i \leq n-1\), \(0 \leq j \leq m-1\)) là ô \((i,j)\). Mỗi ô \((i,j)\) có một chiều cao cụ thể, ký hiệu là \(a[i][j]\).

Hoseyngulu Khan Sardar yêu cầu các kiến trúc sư của mình chọn một khu vực hình chữ nhật để xây dựng cung điện. Khu vực này không được chứa bất kỳ ô nào ở các biên của lưới (hàng \(0\), hàng \(n-1\), cột \(0\) và cột \(m-1\)). Do đó, các kiến trúc sư cần chọn bốn số nguyên \(r_1\), \(r_2\), \(c_1\) và \(c_2\) (\(1 \leq r_1 \leq r_2 \leq n-2\) và \(1 \leq c_1 \leq c_2 \leq m-2\)), xác định một khu vực bao gồm tất cả các ô \((i,j)\) sao cho \(r_1 \leq i \leq r_2\) và \(c_1 \leq j \leq c_2\).

Ngoài ra, một khu vực được coi là hợp lệ khi và chỉ khi mỗi ô \((i,j)\) trong khu vực này thỏa mãn điều kiện sau:

• Xét hai ô liền kề với khu vực này trên hàng \(i\) (ô \((i,c_1-1)\) và ô \((i,c_2+1)\)) và hai ô liền kề với khu vực này trên cột \(j\) (ô \((r_1-1,j)\) và ô \((r_2+1,j)\)). Chiều cao của ô \((i,j)\) phải nhỏ hơn hẳn chiều cao của cả bốn ô này.

Nhiệm vụ của bạn là giúp các kiến trúc sư tìm ra số lượng khu vực hợp lệ cho cung điện (nghĩa là số lượng cách chọn \(r_1\), \(r_2\), \(c_1\) và \(c_2\) xác định một khu vực hợp lệ).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau trong C++, với khai báo trong tệp rect.h:

long long count_rectangles(std::vector<std::vector<int> > a);

• \(a\): một mảng hai chiều các số nguyên có kích thước \(n \times m\), biểu diễn chiều cao các ô.
• Hàm phải trả về số lượng khu vực hợp lệ cho cung điện, dưới dạng số nguyên 64 bit.

Ví dụ

Ví dụ 1

Xét lời gọi sau (viết theo cú pháp C++):

count_rectangles({{4,  8,  7,  5,  6},
                  {7,  4,  10, 3,  5},
                  {9,  7,  20, 14, 2},
                  {9,  14, 7,  3,  6},
                  {5,  7,  5,  2,  7},
                  {4,  5,  13, 5,  6}});

Có \(6\) khu vực hợp lệ được liệt kê dưới đây, vì vậy hàm trả về \(6\):

• \(r_1 = r_2 = c_1 = c_2 = 1\).
• \(r_1 = 1\), \(r_2 = 2\), \(c_1 = c_2 = 1\).
• \(r_1 = r_2 = 1\), \(c_1 = c_2 = 3\).
• \(r_1 = r_2 = 4\), \(c_1 = 2\), \(c_2 = 3\).
• \(r_1 = r_2 = 4\), \(c_1 = c_2 = 3\).
• \(r_1 = 3\), \(r_2 = 4\), \(c_1 = c_2 = 3\).

Ví dụ, \(r_1 = 1\), \(r_2 = 2\), \(c_1 = c_2 = 1\) là một khu vực hợp lệ bởi vì cả hai điều kiện sau đây đều thỏa mãn:

• \(a[1][1] = 4\) nhỏ hơn hẳn \(a[0][1] = 8\), \(a[3][1] = 14\), \(a[1][0] = 7\) và \(a[1][2] = 10\).
• \(a[2][1] = 7\) nhỏ hơn hẳn \(a[0][1] = 8\), \(a[3][1] = 14\), \(a[2][0] = 9\) và \(a[2][2] = 20\).

Ràng buộc

• \(1 \leq n,m \leq 2500\).
• \(0 \leq a[i][j] \leq 7\,000\,000\) với mọi \(0 \leq i \leq n-1\), \(0 \leq j \leq m-1\).
• Giới hạn thời gian: 5 giây.
• Giới hạn bộ nhớ: 1024 MiB.

Chấm điểm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

• Dòng \(1\): \(n\ m\).
• Dòng \(2+i\) (với \(0 \leq i \leq n-1\)): \(a[i][0]\ a[i][1]\ \ldots\ a[i][m-1]\).

Trình chấm mẫu in ra trên một dòng duy nhất giá trị trả về của count_rectangles.

Dữ liệu vào mẫu

6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6

Dữ liệu ra mẫu

6

Nguồn: Đề thi chính thức IOI 2019, ngày thi 1, bài Rectangles (rect); bản tiếng Việt, bản Markdown của ban tổ chức và gói đính kèm chính thức.