#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
long long subtask (vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<vector<int>> psa(n,vector<int>(m));
auto query = [&] (int x, int y, int x2, int y2) {
return psa[x2][y2] - psa[x2][y-1] - psa[x-1][y2] + psa[x-1][y-1];
};
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
psa[i][j] = psa[i-1][j] + psa[i][j-1] - psa[i-1][j-1] + a[i][j];
}
}
int high = 0, low = n, left = m, right = 0;
function<void(int,int)> dfs = [&] (int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || a[x][y]) return;
a[x][y] = 1; high = max(high,x); low = min(low,x); right = max(right,y); left = min(left,y);
dfs(x-1,y); dfs(x+1,y); dfs(x,y+1); dfs(x,y-1);
};
long long ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) if (!a[i][j]) {
high = right = 0;
low = n; left = m;
dfs(i,j);
if (left > 0 && low > 0 && right + 1 < m && high + 1 < n && !query(low,left,high,right)) ++ans;
}
}
return ans;
}
long long count_rectangles (vector<vector<int>> a) {
int mxall = 0;
for (auto &v : a) for (auto &i : v) mxall = max(mxall,i);
if (mxall <= 1) return subtask(a);
int n = a.size(), m = a[0].size();
vector<vector<vector<bool>>> canV(m,vector<vector<bool>>(n,vector<bool>(n)));
vector<vector<vector<bool>>> canH(n,vector<vector<bool>>(m,vector<bool>(m)));
vector<vector<vector<int>>> psaV(n,vector<vector<int>>(n,vector<int>(m)));
vector<vector<vector<int>>> psaH(m,vector<vector<int>>(m,vector<int>(n)));
for (int i = 1; i + 1 < n; i++) {
for (int j = 1; j + 1 < m; j++) {
int mx = a[i][j];
for (int k = j; k + 1 < m; k++) {
mx = max(mx,a[i][k]);
canH[i][j][k] = a[i][j-1] > mx && a[i][k+1] > mx;
}
}
}
for (int j = 1; j + 1 < m; j++) {
for (int k = j; k + 1 < m; k++) {
for (int i = 1; i + 1 < n; i++) {
psaH[j][k][i] = psaH[j][k][i-1] + !canH[i][j][k];
}
}
}
for (int i = 1; i + 1 < m; i++) {
for (int j = 1; j + 1 < n; j++) {
int mx = a[j][i];
for (int k = j; k + 1 < n; k++) {
mx = max(mx,a[k][i]);
canV[i][j][k] = a[j-1][i] > mx && a[k+1][i] > mx;
}
}
}
for (int j = 1; j + 1 < n; j++) {
for (int k = j; k + 1 < n; k++) {
for (int i = 1; i + 1 < m; i++) {
psaV[j][k][i] = psaV[j][k][i-1] + !canV[i][j][k];
}
}
}
long long ans = 0;
for (int i = 1; i + 1 < n; i++) {
for (int j = i; j + 1 < n; j++) { //rows[i --> j]
for (int k = 1; k + 1 < m; k++) {
for (int l = k; l + 1 < m; l++) { //cols[k --> l]
ans += psaV[i][j][l] == psaV[i][j][k-1] && psaH[k][l][j] == psaH[k][l][i-1];
}
}
}
}
return ans;
}
