#include "rect.h"
#include <algorithm>
#include <bits/stdc++.h>
#define int long long
using namespace std;
bool seen[2500][2500];
int DX[] = {-1, 1, 0, 0};
int DY[] = {0, 0, -1, 1};
int nbLig, nbCol;
int maxLig, minLig, minCol, maxCol, nbVus;
vector<vector<signed>> val;
struct maxSeg {
vector<int> seg;
int deb;
maxSeg(int n) {
int p = 0;
while ((1 << p) < n)
++p;
deb = (1 << p);
seg.resize(2 * deb);
}
void upd(int i, int v) {
i += deb;
seg[i] = v;
while (i > 1) {
i /= 2;
seg[i] = max(seg[2 * i], seg[2 * i + 1]);
}
}
int query(int l, int r) {
l += deb, r += deb;
int ret = 0;
while (l < r) {
if (l % 2)
ret = max(ret, seg[l]);
if (r % 2 == 0)
ret = max(ret, seg[r]);
l = (l + 1) / 2;
r = (r - 1) / 2;
}
if (l == r)
ret = max(ret, seg[l]);
return ret;
}
};
struct minSeg {
vector<int> seg;
int deb;
minSeg(int n) {
int p = 0;
while ((1 << p) < n)
++p;
deb = (1 << p);
seg.assign(2 * deb, 1e18);
}
void upd(int i, int v) {
i += deb;
seg[i] = v;
while (i > 1) {
i /= 2;
seg[i] = min(seg[2 * i], seg[2 * i + 1]);
}
}
int query(int l, int r) {
l += deb, r += deb;
int ret = 1e18;
while (l < r) {
if (l % 2)
ret = min(ret, seg[l]);
if (r % 2 == 0)
ret = max(ret, seg[r]);
l = (l + 1) / 2;
r = (r - 1) / 2;
}
if (l == r)
ret = min(ret, seg[l]);
return ret;
}
};
void dfs(int iLig, int iCol) {
if (nbLig <= iLig or iLig < 0 or iCol < 0 or iCol >= nbCol or
seen[iLig][iCol] or val[iLig][iCol])
return;
nbVus++;
maxLig = max(maxLig, iLig);
minLig = min(minLig, iLig);
minCol = min(minCol, iCol);
maxCol = max(maxCol, iCol);
seen[iLig][iCol] = true;
for (int d = 0; d < 4; ++d) {
int col = iCol + DX[d];
int lig = iLig + DY[d];
dfs(lig, col);
}
}
int solveBinary() {
int ret = 0;
for (int iLig = 0; iLig < nbLig; ++iLig)
for (int iCol = 0; iCol < nbCol; ++iCol)
if (!seen[iLig][iCol] and !val[iLig][iCol]) {
minLig = maxLig = iLig;
minCol = maxCol = iCol;
nbVus = 0;
dfs(iLig, iCol);
ret += nbVus == (maxLig - minLig + 1) * (maxCol - minCol + 1) and
maxLig < nbLig - 1 and minLig > 0 and minCol > 0 and
maxCol < nbCol - 1;
}
return ret;
}
int count_rectangles(vector<vector<signed>> a) {
val = a;
nbLig = a.size(), nbCol = a[0].size();
bool isBinary = true;
for (auto v : a)
for (auto w : v)
isBinary &= w < 2;
if (isBinary)
return solveBinary();
vector<vector<int>> down(nbLig, vector<int>(nbCol));
vector<vector<int>> up(nbLig, vector<int>(nbCol));
vector<vector<int>> right(nbLig, vector<int>(nbCol));
vector<vector<int>> left(nbLig, vector<int>(nbCol));
for (int col = 0; col < nbCol; ++col) {
for (int iLig = nbLig - 1; iLig >= 0; --iLig) {
int nxt = iLig + 1;
while (nxt < nbLig and a[iLig][col] > a[nxt][col])
nxt = down[nxt][col];
down[iLig][col] = nxt;
}
for (int iLig = 0; iLig < nbLig; ++iLig) {
int nxt = iLig - 1;
while (nxt >= 0 and a[iLig][col] > a[nxt][col])
nxt = up[nxt][col];
up[iLig][col] = nxt;
}
}
for (int lig = 0; lig < nbLig; ++lig) {
for (int iCol = nbCol - 1; iCol >= 0; --iCol) {
int nxt = iCol + 1;
while (nxt < nbCol and a[lig][iCol] > a[lig][nxt])
nxt = right[lig][nxt];
right[lig][iCol] = nxt;
}
for (int iCol = 0; iCol < nbCol; ++iCol) {
int nxt = iCol - 1;
while (nxt >= 0 and a[lig][iCol] > a[lig][nxt])
nxt = left[lig][nxt];
left[lig][iCol] = nxt;
}
}
vector<minSeg> segRight(nbCol, minSeg(nbLig));
vector<maxSeg> segLeft(nbCol, maxSeg(nbLig));
for (int iLig = 0; iLig < nbLig; ++iLig)
for (int iCol = 0; iCol < nbCol; ++iCol) {
segRight[iCol].upd(iLig, right[iLig][iCol]);
segLeft[iCol].upd(iLig, left[iLig][iCol]);
}
int sol = 0;
for (int lig1 = 0; lig1 < nbLig; ++lig1)
for (int lig2 = lig1 + 2; lig2 < nbLig; ++lig2) {
vector<int> minRight(nbCol), maxLeft(nbCol);
for (int iCol = 0; iCol < nbCol; ++iCol) {
minRight[iCol] = nbCol - 1;
maxLeft[iCol] = 0;
for (int i = lig1 + 1; i < lig2; ++i) {
minRight[iCol] = min(minRight[iCol], right[i][iCol]);
maxLeft[iCol] = max(maxLeft[iCol], left[i][iCol]);
}
}
for (int col1 = 0; col1 < nbCol; ++col1) {
int bnd = segRight[col1].query(lig1 + 1, lig2 - 1);
for (int col2 = col1 + 2; col2 < nbCol and col2 <= bnd; ++col2) {
if (up[lig2][col2 - 1] > lig1 or down[lig1][col2 - 1] < lig2)
break;
bool ok = segLeft[col2].query(lig1 + 1, lig2 - 1) <= col1;
sol += ok;
}
}
}
return sol;
}
