#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, t;
pair <int, int> hor_l[2500][2500], hor_r[2500][2500];
pair <int, int> ver_u[2500][2500], ver_d[2500][2500];
vector < array <int, 4> > v;
vector < array <int, 4> > bucket[2500];
struct window : vector < pair <int, int> > {
void append (int x) {
while (!empty () && back ().first < x) pop_back ();
}
};
void check_above (pair <int, int>& p, int i, int l, int r) {
if (!i) return;
if (hor_l[i-1][r].first == l) p.second += hor_l[i-1][r].second;
else if (hor_r[i-1][l].first == r) p.second += hor_r[i-1][l].second;
}
void check_left (pair <int, int>& p, int u, int d, int j) {
if (!j) return;
if (ver_d[u][j-1].first == d) p.second += ver_d[u][j-1].second;
else if (ver_u[d][j-1].first == u) p.second += ver_u[d][j-1].second;
}
void check_rectangle (vector < vector <int> >& a, int x1, int y1, int x2, int y2) {
if (x2 - x1 < 2 || y2 - y1 < 2) return;
int hor_size, ver_size;
if (a[x2-1][y1] <= a[x2-1][y2]) {
if (hor_r[x2-1][y1].first != y2) return;
ver_size = hor_r[x2-1][y1].second;
}
else {
if (hor_l[x2-1][y2].first != y1) return;
ver_size = hor_l[x2-1][y2].second;
}
if (a[x1][y2-1] <= a[x2][y2-1]) {
if (ver_d[x1][y2-1].first != x2) return;
hor_size = ver_d[x1][y2-1].second;
}
else {
if (ver_u[x2][y2-1].first != x1) return;
hor_size = ver_u[x2][y2-1].second;
}
if ((hor_size >= y2 - y1 - 1) && (ver_size >= x2 - x1 - 1)) {
//cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << ' ' << ver_u[x2][y2-1].first << endl;
v.push_back ({x1, y1, x2, y2});
}
}
void check_position (vector< vector <int> >& a, int i, int l, int r) {
int x;
if (r - l < 2) return;
x = ver_u[i+1][l+1].first;
if (x != -1) check_rectangle (a, x, l, i + 1, r);
x = ver_d[i-1][l+1].first;
if (x != -1) check_rectangle (a, i - 1, l, x, r);
x = ver_u[i+1][r-1].first;
if (x != -1) check_rectangle (a, x, l, i + 1, r);
x = ver_d[i-1][r-1].first;
if (x != -1) check_rectangle (a, i - 1, l, x, r);
}
ll count_bruteforce (vector <vector <int>>& a) {
int ans = 0;
for (int i = 1; i < n - 1; i++)
for (int j = 1; j < m - 1; j++)
for (int i1 = i; i1 < n - 1; i1++)
for (int j1 = j; j1 < m - 1; j1++) {
bool k = true;
for (int i0 = i; i0 <= i1; i0++)
for (int j0 = j; j0 <= j1; j0++) {
if (a[i0][j0] >= a[i-1][j0] || a[i0][j0] >= a[i1+1][j0] ||
a[i0][j0] >= a[i0][j-1] || a[i0][j0] >= a[i0][j1+1]) k = false;
}
if (k) {
ans++;
}
}
return ans;
}
ll count_rectangles (vector<vector<int> > a) {
n = a.size (), m = a[0].size ();
while (true) {
//for (int i = 0; i < n; i++)
// for (int j = 0; j < m; j++)
// a[i][j] = rand () % 11;
window s;
for (int i = 0; i < n; i++) {
s.clear ();
for (int j = 0; j < m; j++) {
s.append (a[i][j]);
if (!s.empty ()) {
int l = s.back ().second, r = j;
hor_l[i][r].first = l;
hor_l[i][r].second = 1;
check_above (hor_l[i][r], i, l, r);
} else hor_l[i][j].first = -1;
s.push_back ({a[i][j], j});
}
s.clear ();
for (int j = m - 1; j >= 0; j--) {
s.append (a[i][j]);
if (!s.empty ()) {
int l = j, r = s.back ().second;
hor_r[i][l].first = r;
hor_r[i][l].second = 1;
check_above (hor_r[i][l], i, l, r);
} else hor_r[i][j].first = -1;
s.push_back ({a[i][j], j});
}
}
for (int j = 0; j < m; j++) {
s.clear ();
for (int i = 0; i < n; i++) {
s.append (a[i][j]);
if (!s.empty ()) {
int u = s.back ().second, d = i;
ver_u[d][j].first = u;
ver_u[d][j].second = 1;
check_left (ver_u[d][j], u, d, j);
} else ver_u[i][j].first = -1;
s.push_back ({a[i][j], i});
}
s.clear ();
for (int i = n - 1; i >= 0; i--) {
s.append (a[i][j]);
if (!s.empty ()) {
int u = i, d = s.back ().second;
ver_d[u][j].first = d;
ver_d[u][j].second = 1;
check_left (ver_d[u][j], u, d, j);
} else ver_d[i][j].first = -1;
s.push_back ({a[i][j], i});
}
}
for (int i = 1; i < n - 1; i++) {
for (int j = 0; j < m; j++) {
if (hor_l[i][j].first != -1) check_position (a, i, hor_l[i][j].first, j);
if (hor_r[i][j].first != -1) check_position (a, i, j, hor_r[i][j].first);
}
}
for (int k = 0; k < 4; k++) {
for (int i = 0; i < max (n, m); i++)
bucket[i].clear ();
for (auto&& a : v) {
bucket[a[k]].push_back (a);
}
v.clear ();
for (int i = 0; i < max (n, m); i++)
for (auto&& a : bucket[i])
v.push_back (a);
}
int cnt = 0;
for (int i = 0; i < (int) v.size (); i++)
if (!i || v[i-1] != v[i]) cnt++;
v.clear ();
int cnt2 = -1;
t++;
if (t % 100 == 0) cout << t << endl;
//cout << cnt << ' ' << cnt2 << endl;
if (cnt != cnt2) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << a[i][j] << ' ';
cout << '\n';
}
return cnt;
}
return cnt;
}
}
