#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 9'900'000;
vector<int> lo_range;
vector<int> hi_range;
struct dset
{
set<int> regular;
set<int> inverted;
void insert_both(int a)
{
regular.insert(a);
inverted.insert(0-a);
}
void get_range(int a)
{
int hi = *(regular.upper_bound(a));
int lo = 0-*(inverted.upper_bound(0-a));
lo_range[a] = lo;
hi_range[a] = hi;
}
dset(int a, int b)
{
regular = {};
inverted = {};
insert_both(a);
insert_both(b);
}
void process_same_height(vector<int> (&x))
{
for (int a: x)
get_range(a);
for (int a: x)
insert_both(a);
}
};
struct cell
{
int r;
int c;
int lor, hir;
int loc, hic;
vector<int> rbased;
vector<int> cbased;
bool valid;
void update()
{
rbased = {lor, hir, c, r};
cbased = {loc, hic, r, c};
valid = 1;
}
void check_validity_r(int min_r, int max_r)
{
if (lor < (min_r-1))
{
valid = 0;
//cout << r << ' ' << c << " disqualified by check_validity_r\n";
}
if (hir > (max_r+1))
{
valid = 0;
//cout << r << ' ' << c << " disqualified by check_validity_r\n";
}
}
void check_validity_c(int min_c, int max_c)
{
if (loc < (min_c-1))
{
valid = 0;
//cout << r << ' ' << c << " disqualified by check_validity_c\n";
}
if (hic > (max_c+1))
{
valid = 0;
//cout << r << ' ' << c << " disqualified by check_validity_c\n";
}
}
};
vector<vector<cell>> grid;
void c_process(vector<vector<int>> (&x))
{
int siz = x.size();
x.push_back({-1, -1, INF, INF, -1, -1});
int curr_l = 0;
int curr_r = 0;
for (int i=1; i<=siz; i++)
{
if ((x[i][2] - x[i-1][2]) <= 1)
curr_r = i;
else
{
int range_l = x[curr_l][2];
int range_r = x[curr_r][2];
for (int j=curr_l; j<=curr_r; j++)
grid[x[j][2]][x[j][3]].check_validity_r(range_l, range_r);
curr_l = i;
curr_r = i;
}
}
}
void r_process(vector<vector<int>> (&x))
{
int siz = x.size();
x.push_back({-1, -1, INF, INF, -1, -1});
int curr_l = 0;
int curr_r = 0;
for (int i=1; i<=siz; i++)
{
if ((x[i][2] - x[i-1][2]) <= 1)
curr_r = i;
else
{
int range_l = x[curr_l][2];
int range_r = x[curr_r][2];
for (int j=curr_l; j<=curr_r; j++)
grid[x[j][3]][x[j][2]].check_validity_c(range_l, range_r);
curr_l = i;
curr_r = i;
}
}
}
long long count_rectangles(std::vector< std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
//phase 1: fill the grid of cells with the info i need
grid = vector<vector<cell>> (n, vector<cell> (m));
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
{
grid[i][j].r=i;
grid[i][j].c=j;
}
for (int row = 0; row<n; row++)
{
dset worker(-1, m);
vector<pair<int, int>> row_heights;
for (int j = 0; j<m; j++)
row_heights.push_back({a[row][j], j});
sort(row_heights.begin(), row_heights.end(), greater<pair<int, int>>());
row_heights.push_back({-1, -1});
lo_range = vector<int> (m);
hi_range = vector<int> (m);
vector<int> to_insert = {row_heights[0].second};
for (int k=1; k<=m; k++)
{
if (row_heights[k-1].first == row_heights[k].first)
to_insert.push_back(row_heights[k].second);
else
{
worker.process_same_height(to_insert);
to_insert = {row_heights[k].second};
}
}
for (int j = 0; j<m; j++)
{
grid[row][j].loc = lo_range[j];
grid[row][j].hic = hi_range[j];
}
}
for (int col = 0; col<m; col++)
{
dset worker(-1, n);
vector<pair<int, int>> col_heights;
for (int i = 0; i<n; i++)
col_heights.push_back({a[i][col], i});
sort(col_heights.begin(), col_heights.end(), greater<pair<int, int>>());
col_heights.push_back({-1, -1});
lo_range = vector<int> (n);
hi_range = vector<int> (n);
vector<int> to_insert = {col_heights[0].second};
for (int k=1; k<=n; k++)
{
if (col_heights[k-1].first == col_heights[k].first)
to_insert.push_back(col_heights[k].second);
else
{
worker.process_same_height(to_insert);
to_insert = {col_heights[k].second};
}
}
for (int i = 0; i<n; i++)
{
grid[i][col].lor = lo_range[i];
grid[i][col].hir = hi_range[i];
}
}
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
{
grid[i][j].update();
cell x = grid[i][j];
//cout << x.r << ' ' << x.c << ' ' << x.lor << ' ' << x.hir << ' ' << x.loc << ' ' << x.hic << '\n';
}
//phase 2
vector<vector<int>> cbasedlist;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
cbasedlist.push_back(grid[i][j].cbased);
sort(cbasedlist.begin(), cbasedlist.end());
cbasedlist.push_back({-1, -1, -1, -1});
vector<vector<int>> to_process = {cbasedlist[0]};
for (int ij = 1; ij <= (m*n); ij++)
{
if ((cbasedlist[ij][0]==cbasedlist[ij-1][0]) and (cbasedlist[ij][1]==cbasedlist[ij-1][1]))
to_process.push_back(cbasedlist[ij]);
else
{
c_process(to_process);
to_process = {cbasedlist[ij]};
}
}
cbasedlist.clear();
vector<vector<int>> rbasedlist;
for (int i=0; i<n; i++)
for (int j=0; j<m; j++)
rbasedlist.push_back(grid[i][j].rbased);
sort(rbasedlist.begin(), rbasedlist.end());
rbasedlist.push_back({-1, -1, -1, -1});
to_process = {rbasedlist[0]};
for (int ij = 1; ij <= (m*n); ij++)
{
if ((rbasedlist[ij][0]==rbasedlist[ij-1][0]) and (rbasedlist[ij][1]==rbasedlist[ij-1][1]))
to_process.push_back(rbasedlist[ij]);
else
{
r_process(to_process);
to_process = {rbasedlist[ij]};
}
}
rbasedlist.clear();
//finding answer
set<vector<int>> valid_rectangles;
for (int i=1; i<(n-1); i++)
for (int j=1; j<(m-1); j++)
{
cell x = grid[i][j];
if (x.valid and (x.lor!=-1) and (x.hir!=n) and (x.loc!=-1) and (x.hic!=m))
{
valid_rectangles.insert({x.lor, x.hir, x.loc, x.hic});
//cout << x.lor << ' ' << x.hir << ' ' << x.loc << ' ' << x.hic << '\n';
}
}
long long answer = valid_rectangles.size();
return answer;
}
