#include "rect.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
long long count_rectangles(vector<vector<int>> a) {
long long ans = 0;
int n = a.size();
int m = a[0].size();
if (n <= 2) return 0;
if (m <= 2) return 0;
bool oneorzero = true;
for (auto i : a) {
for (int j : i) {
oneorzero &= (j <= 1);
}
}
if (n <= 3) {
vector<int> ok(m);
for (int i = 1; i < m - 1; i++) ok[i] = (a[0][i] > a[1][i] && a[2][i] > a[1][i]);
for (int i = 1; i < m - 1; i++) {
int cur_max = 0;
for (int j = i; j < m - 1; j++) {
if (!ok[j]) break;
cur_max = max(cur_max, a[1][j]);
if (a[1][i - 1] > cur_max && a[1][j + 1] > cur_max) ans++;
}
}
return ans;
}
if (oneorzero) {
vector<vector<int>> p(n + 1, vector<int> (m + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + (a[i - 1][j - 1] ^ 1);
}
}
auto sum = [&](int i, int j, int ii, int jj) {
return p[ii][jj] - p[i - 1][jj] - p[ii][j - 1] + p[i - 1][j - 1];
};
vector<vector<int>> row(n, vector<int> (m));
vector<vector<int>> col(m, vector<int> (n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
row[i][j] = (j == 0 ? 0 : row[i][j - 1]) + a[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
col[i][j] = (j == 0 ? 0 : col[i][j - 1]) + a[j][i];
}
}
vector<vector<int>> to_right(n, vector<int> (m));
auto to_down = to_right;
for (int i = 0; i < n; i++) {
for (int j = m - 1; j >= 0; j--) {
if (a[i][j] == 1) to_right[i][j] = j;
else to_right[i][j] = (j == m - 1 ? m : to_right[i][j + 1]);
}
}
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 1) to_down[i][j] = i;
else to_down[i][j] = (i == n - 1 ? n : to_down[i + 1][j]);
}
}
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
if (a[i][j]) continue;
if (to_right[i][j] >= m) continue;
if (to_down[i][j] >= n) continue;
int r = to_right[i][j], d = to_down[i][j];
if (row[i - 1][r - 1] - row[i - 1][j - 1] != r - j) continue;
if (row[d][r - 1] - row[d][j - 1] != r - j) continue;
if (col[r][d - 1] - col[r][i - 1] != d - i) continue;
if (col[j - 1][d - 1] - col[j - 1][i - 1] != d - i) continue;
if (sum(i + 1, j + 1, d, r) != (d - i) * (r - j)) continue;
ans++;
}
}
return ans;
}
int max_val[n][n][m];
bool good[n][n][m];
memset(max_val, 0, sizeof max_val);
memset(good, 0, sizeof good);
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
for (int ii = i; ii < n - 1; ii++) {
max_val[i][ii][j] = (i == ii ? a[i][j] : max(a[ii][j], max_val[i][ii - 1][j]));
good[i][ii][j] = (max_val[i][ii][j] < min(a[i - 1][j], a[ii + 1][j]));
}
}
}
int mx[m][m][n];
bool gg[m][m][n];
memset(mx, 0, sizeof mx);
memset(gg, 0, sizeof gg);
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
for (int ii = i; ii < m - 1; ii++) {
mx[i][ii][j] = (i == ii ? a[j][i] : max(a[j][ii], mx[i][ii - 1][j]));
gg[i][ii][j] = (mx[i][ii][j] < min(a[j][i - 1], a[j][ii + 1]));
}
}
}
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
for (int ii = i; ii < n - 1; ii++) {
for (int jj = j; jj < m - 1; jj++) {
if (!good[i][ii][jj]) break;
bool g = true;
for (int x = i; x <= ii; x++) g &= gg[j][jj][x];
if (g) ans++;
}
}
}
}
return ans;
}
