#include "rect.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<bitset>
#include<utility>
using namespace std;
typedef long long ll;
long long count_rectangles(std::vector<std::vector<int> > a) {
ll ans = 0;
int n = (int)a.size();
int m = (int)a[0].size();
if(n <= 2 || m <= 2) return 0;
vector<vector<int>> pre(n, vector<int>(m));
pre[0][0] = a[0][0];
for(int i = 1; i < n; i++) pre[i][0] = pre[i - 1][0] + a[i][0];
for(int i = 1; i < m; i++) pre[0][i] = pre[0][i - 1] + a[0][i];
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++) pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + a[i][j];
}
auto calc = [&](int a, int b, int c, int d){
int res = pre[b][d];
if(c > 0) res -= pre[b][c - 1];
if(a > 0) res -= pre[a - 1][d];
if(c > 0 && a > 0) res += pre[a - 1][c - 1];
return res;
};
vector<vector<int>> lstr(n, vector<int>(m)), lstc(n, vector<int>(m));
for(int i = 1; i < n - 1; i++){
lstr[i][0] = 1;
for(int j = 1; j < m - 1; j++){
if(a[i][j] == 0 && a[i + 1][j] == 1){
if(lstr[i][j - 1] == -1) lstr[i][j] = j;
else lstr[i][j] = lstr[i][j - 1];
}
else lstr[i][j] = -1;
}
}
for(int i = 1; i < m - 1; i++){
lstc[0][i] = 1;
for(int j = 1; j < n - 1; j++){
if(a[j][i] == 0 && a[j][i + 1] == 1){
if(lstc[j - 1][i] == -1) lstc[j][i] = j;
else lstc[j][i] = lstc[j - 1][i];
}
else lstc[j][i] = -1;
}
}
for(int i = 1; i < n - 1; i++){
for(int j = 1; j < m - 1; j++){
if(lstr[i][j] >= 0 && lstc[i][j] >= 0){
int a = lstc[i][j], b = i, c = lstr[i][j], d = j;
if(calc(a, b, c, d) == 0 && calc(a, b, c - 1, c - 1) == b - a + 1 && calc(a, b, d + 1, d + 1) == b - a + 1 && calc(a - 1, a - 1, c, d) == d - c + 1 && calc(b + 1, b + 1, c, d) == d - c + 1) ans++;
}
}
}
return ans;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run rect2.cpp grader.cpp
