#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#include "rect.h"
using namespace std;
constexpr static int UP = 0;
constexpr static int DOWN = 1;
constexpr static int LEFT = 2;
constexpr static int RIGHT = 3;
constexpr static int MXN = 2505;
struct Fenwick
{
int v[MXN];
int get(int i) { int res = 0; for (++i; i > 0; i-=i&(-i)) res += v[i]; return res; }
void set(int i, int val) { for (++i; i < MXN; i+=i&(-i)) v[i] += val; }
int get(int l, int r) { return get(r) - get(l); }
void reset() { fill(v, v + MXN, 0); }
};
int vals[MXN][MXN][4];
void calculate_cell(int i, int j, const vector<vector<int32_t>>& a)
{
int ii, jj;
for (ii = max<int>(i-1, 0); ii > 0; ii--)
if (a[ii][j] >= a[i][j])
break;
vals[i][j][UP] = ii;
for (ii = min<int>(i+1, a.size()-1); ii < a.size() - 1; ii++)
if (a[ii][j] >= a[i][j])
break;
vals[i][j][DOWN] = ii;
for (jj = max<int>(j-1, 0); jj > 0; jj--)
if (a[i][jj] >= a[i][j])
break;
vals[i][j][LEFT] = jj;
for (jj = min<int>(j+1, a[0].size()-1); jj < a[0].size() - 1; jj++)
if (a[i][jj] >= a[i][j])
break;
vals[i][j][RIGHT] = jj;
}
int first[MXN];
int last[MXN];
int nxt[MXN];
Fenwick fw;
int pf[MXN][MXN];
bitset<MXN> visited[MXN];
void check_try(int i, int j, queue<array<int, 2>>& q, vector<vector<int32_t>>& a)
{
if (i < a.size() && i >=0 && j < a[0].size() && j >= 0 && !visited[i][j] && a[i][j] == 0)
{
visited[i][j] = true;
q.push({i, j});
}
}
long long special_subtask(vector<vector<int32_t>>& a)
{
for (int i = 1; i <= a.size(); i++)
for (int j = 1; j <= a[0].size(); j++)
pf[i][j] = pf[i][j-1] + pf[i-1][j] - pf[i-1][j-1] + a[i-1][j-1];
int res = 0;
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < a[0].size(); j++)
{
if (visited[i][j] || a[i][j] == 1)
continue;
queue<array<int, 2>> q;
q.push({i, j});
int up = MXN;
int down = -1;
int left = MXN;
int right = -1;
while (q.size())
{
auto [ii, jj] = q.front();
q.pop();
check_try(ii+1, jj, q, a);
check_try(ii, jj+1, q, a);
check_try(ii, jj-1, q,a );
check_try(ii-1, jj, q,a );
up = min(up, ii);
down = max(down, ii);
left = min(left, jj);
right = max(right, jj);
}
if (pf[down+1][right+1] - pf[down+1][left] - pf[up][right+1] + pf[up][left] == 0 && down < a.size() - 1&& up > 0 && right < a[0].size() -1 && left > 0)
res++;
}
}
return res;
}
long long count_rectangles(vector<vector<int32_t>> a)
{
if (a.size() > 200)
return special_subtask(a);
for (int i = 0; i < a.size(); i++)
{
for (int j = 0; j < a[0].size(); j++)
{
calculate_cell(i, j, a);
}
}
int res = 0;
for (int u = 0; u < a.size()-1; u++)
{
fill(first, first + MXN, 0);
fill(last, last + MXN, MXN);
for (int d = u+2; d < a.size(); d++)
{
fw.reset();
for (int i = 0; i < a[0].size(); i++)
first[i] = max<int>(first[i], vals[d-1][i][LEFT]); // Getting the leftmost possible for each of them
for (int i = 0; i < a[0].size(); i++)
last[i] = min<int>(last[i], vals[d-1][i][RIGHT]);
vector<vector<int>> rrr(a[0].size());
for (int i = 0; i < a[0].size(); i++)
rrr[first[i]].pb(i);
vector<int> pending;
for (int i = 0; i < a[0].size(); i++)
{
pending.pb(i);
if (vals[u][i][DOWN] < d || vals[d][i][UP] > u)
{
for (int j : pending)
nxt[j] = i;
pending.clear();
}
}
for (int j : pending)
nxt[j] = a[0].size();
for (int i = 0; i < a[0].size(); i++)
{
for (int j : rrr[i])
{
fw.set(j, 1);
}
if (min(last[i], nxt[i+1]) > i+1)
{
res += fw.get(i+1, min(last[i], nxt[i+1]));
}
}
}
}
return res;
}
