#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
typedef long long ll;
const int MX = 2505;
int cl[MX][MX]; // smallest row>i on same column containing one
int nxt[MX][MX]; // furthest col on same row tel que same close
int cum[MX][MX]; // normal cum on columns
int gimme(int col,int a,int b){
return cum[b][col] - (a?cum[a-1][col]:0);
}
ll count_rectangles(vector<vector<int> > a) {
ll ans=0;
int n=sz(a),m=sz(a[0]);
for (int j = 0; j < m; ++j)
{
int last=-1;
for (int i = n-1; i >= 0; i--)
if(a[i][j]){
cl[i][j]=last,last=i;
if((i+1) ==cl[i][j])cl[i][j]=-1;
}
}
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; )
{
if(!a[i][j]){
cum[i][j]=(!a[i][j]);
if(i)cum[i][j]+=cum[i-1][j];
nxt[i][j]=-1,j++;
continue;
}
int z=j;
while(z<m && cl[i][z]==cl[i][j])
z++;
for (int A = j; A < z; ++A){
cum[i][A]=(!a[i][A]);
if(i)cum[i][A]+=cum[i-1][A];
nxt[i][A]=z;
}
j=z;
}
for (int i = 0; i < n-2; ++i)
for (int j = 1; j < m-1; ++j)
if(a[i][j] && cl[i][j]!=-1 && !gimme(j-1,i+1,cl[i][j]-1) && !gimme(nxt[i][j],i+1,cl[i][j]-1))
ans++;
return ans;
}
