#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 2505;
ll Left[N][N];
ll Down[N][N];
vector < ll > Row[N], Col[N];
ll sum[N][N];
ll req(ll x1, ll y1, ll x2, ll y2){
return sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
}
long long count_rectangles(std::vector<std::vector<int> > a) {
ll n = a.size();
ll m = a[0].size();
if(min(n, m) < 3) return 0;
n -= 2; m -= 2; ll ans = 0;
for(ll i = 1; i <= n; i++){
ll last = m;
for(ll j = m; j >= 1; j--){
if(a[i][j] == 0){
Left[i][j] = last;
continue;
}
last = j - 1;
}
}
for(ll j = 1; j <= m; j++){
ll last = n;
for(ll i = n; i >= 1; i--){
if(a[i][j] == 0){
Down[i][j] = last;
continue;
}
last = i - 1;
}
}
for(ll i = 0; i <= n + 1; i++){
for(ll j = 0; j <= m + 1; j++){
if(a[i][j] == 0){
Row[i].pb(j);
Col[j].pb(i);
}
sum[i][j] = a[i][j];
if(j) sum[i][j] += sum[i][j - 1];
}
}
for(ll j = 0; j <= m + 1; j++){
for(ll i = 0; i <= n + 1; i++){
if(i) sum[i][j] += sum[i - 1][j];
}
}
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= m; j++){
if(a[i][j]) continue;
ll x = Down[i][j], y = Left[i][j];
// (i, j) -- (x, y)
auto it1 = lower_bound(Row[i-1].begin(), Row[i-1].end(), j);
if(it1 != Row[i-1].end() && *it1 <= y) continue;
auto it2 = lower_bound(Row[x+1].begin(), Row[x+1].end(), j);
if(it2 != Row[x+1].end() && *it2 <= y) continue;
auto it3 = lower_bound(Col[j-1].begin(), Col[j-1].end(), i);
if(it3 != Col[j-1].end() && *it3 <= x) continue;
auto it4 = lower_bound(Col[y+1].begin(), Col[y+1].end(), i);
if(it4 != Col[y+1].end() && *it4 <= x) continue;
if(req(i, j, x, y) == 0) ans++;
}
}
return ans;
}
