#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
ll n, m;
ll pow2N, pow2M;
vector<vector<ll>> segN, segM;
ll segMaxN(ll low, ll high, ll m) {
low += pow2N; high += pow2N;
ll mx = 0;
while (low <= high) {
if (low & 1) mx = max(mx, segN[m][low++]);
if (!(high & 1)) mx = max(mx, segN[m][high--]);
low /= 2; high /= 2;
}
return mx;
}
ll segMaxM(ll low, ll high, ll n) {
low += pow2M; high += pow2M;
ll mx = 0;
while (low <= high) {
if (low & 1) mx = max(mx, segM[n][low++]);
if (!(high & 1)) mx = max(mx, segM[n][high--]);
low /= 2; high /= 2;
}
return mx;
}
ll otherSol(vector<vector<int>> a) {
if (a.size() <= 2) return 0;
n = a.size(); m = a[0].size();
pow2N = 1ll << (ll)ceil(log2(n));
pow2M = 1ll << (ll)ceil(log2(m));
vector<int> am = a[1];
segN = vector<vector<ll>>(m, vector<ll>(2*pow2N));
segM = vector<vector<ll>>(n, vector<ll>(2*pow2M));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
segN[j][pow2N+i] = a[i][j];
segM[i][pow2M+j] = a[i][j];
}
}
for (int meta = 0; meta < n; meta++) {
for (int i = pow2M-1; i > 0; i--) {
segM[meta][i] = max(segM[meta][2*i], segM[meta][2*i+1]);
}
}
for (int meta = 0; meta < m; meta++) {
for (int i = pow2N-1; i > 0; i--) {
segN[meta][i] = max(segN[meta][2*i], segN[meta][2*i+1]);
}
}
ll res = 0;
for (int lN = 1; lN <= n; lN++) {
for (int lM = 1; lM <= m; lM++) {
for (int i = 1; i+lN-1 < n-1; i++) {
for (int j = 1; j+lM-1 < m-1; j++) {
bool poss = 1;
for (int meta = i; meta < i+lN && poss; meta++) {
ll border = min(a[meta][j-1], a[meta][j+lM]);
if (border <= segMaxM(j, j+lM-1, meta)) {
poss = 0;
}
}
for (int meta = j; meta < j+lM && poss; meta++) {
ll border = min(a[i-1][meta], a[i+lN][meta]);
if (border <= segMaxN(i, i+lN-1, meta)) {
poss = 0;
}
}
res += poss;
if (poss) j += lM;
}
}
}
}
return res;
}
ll count_rectangles(vector<vector<int>> a) {
if (a.size() <= 2) return 0;
n = a.size(); m = a[0].size();
if (n <= 3 || (n <= 80 && m <= 80)) {
return otherSol(a);
}
vector<vector<bool>> vst(n, vector<bool>(m));
ll res = 0;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
if (a[i][j] || vst[i][j]) continue;
ll ptrN = i, ptrM = j;
while (!a[ptrN][ptrM] && ptrM < m-1) ptrM++;
ptrM--;
while (!a[ptrN][ptrM] && ptrN < n-1) ptrN++;
ptrN--;
bool poss = true;
for (int x = i; x <= ptrN && poss; x++) {
for (int y = j; y <= ptrM && poss; y++) {
vst[x][y] = true;
if (a[x][y]) poss = false;
}
}
for (int x = i; x <= ptrN && poss; x++) {
if (!a[x][j-1]) poss = false;
if (!a[x][ptrM+1]) poss = false;
}
for (int y = j; y <= ptrM && poss; y++) {
if (!a[i-1][y]) poss = false;
if (!a[ptrN+1][y]) poss = false;
}
res += poss;
}
}
return res;
}
