#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 700;
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size(), m = a[0].size();
// vector<basic_string<vector<short>>> pref1(m, vector<vector<short>>(n, vector<short>(n)));
ll ans = 0;
vector<vector<int>> pref(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
pref[i][j] = a[i - 1][j - 1] + pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1];
}
auto get = [&](int x1, int y1, int x2, int y2) -> int {
return pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
};
auto full = [&](int x1, int y1, int x2, int y2) -> int {
int sum = pref[x2][y2] - pref[x2][y1 - 1] - pref[x1 - 1][y2] + pref[x1 - 1][y1 - 1];
return sum == (x2 - x1 + 1) * (y2 - y1 + 1);
};
for (int i = 2; i < n; i++) for (int j = 2; j < m; j++) {
if (a[i - 1][j - 1]) continue;
int lx = j, rx = m - 1, best1 = -1, best2 = -1;
while (lx <= rx) {
int mid = (lx + rx) >> 1;
if (get(i, j, i, mid) == 0) {
best2 = mid;
lx = mid + 1;
} else {
rx = mid - 1;
}
}
lx = i, rx = n - 1;
while (lx <= rx) {
int mid = (lx + rx) >> 1;
if (get(i, j, mid, j) == 0) {
best1 = mid;
lx = mid + 1;
} else {
rx = mid - 1;
}
}
// cout << i << ' ' << j << ' ' << best1 << ' ' << best2 << endl;
assert(best1 != -1 and best2 != -1);
if (get(i, j, best1, best2)) continue;
if (!full(i - 1, j, i - 1, best2)) continue;
if (!full(best1 + 1, j, best1 + 1, best2)) continue;
if (!full(i, j - 1, best1, j - 1)) continue;
if (!full(i, best2 + 1, best1, best2 + 1)) continue;
ans++;
}
return ans;
}
