#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
const int N = 2500 + 7;
int v[N];
int stk[N];
int top;
int l[N];
int r[N];
vector<pair<int, int>> potential(vector<int> b)
{
int n = (int) b.size();
for (int i = 1; i <= n;i ++)
{
v[i] = b[i - 1];
}
top = 0;
stk[0] = 0;
for (int i = 1; i <= n; i++)
{
while (top && v[stk[top]] < v[i])
{
top--;
}
l[i] = stk[top];
stk[++top] = i;
}
top = 0;
stk[0] = n + 1;
for (int i = n; i >= 1; i--)
{
while (top && v[stk[top]] <= v[i])
{
top--;
}
r[i] = stk[top];
stk[++top] = i;
}
vector<pair<int, int>> sol;
for (int i = 1; i <= n; i++)
{
int j = l[i];
if (1 <= j && i - j >= 2)
{
sol.push_back({j, i});
}
j = r[i];
if (j <= n && j - i >= 2)
{
sol.push_back({i, j});
}
}
for (auto &it : sol)
{
it.first--;
it.second--;
it.first++;
it.second--;
}
sort(sol.begin(), sol.end());
return sol;
}
void print(vector<pair<int, int>> a)
{
for (auto &it : a)
{
cout << " : " << it.first << " " << it.second << "\n";
}
}
vector<vector<pair<int, int>>> pot_row;
vector<vector<pair<int, int>>> pot_col;
bool has(int c, int r1, int r2)
{
pair<int, int> it = {r1, r2};
int lo = 0;
int hi = (int) pot_col[c].size() - 1;
while (lo <= hi)
{
int mid = (lo + hi) / 2;
if (pot_col[c][mid] == it)
{
return 1;
}
if (pot_col[c][mid] < it)
{
lo = mid + 1;
}
else
{
hi = mid - 1;
}
}
return 0;
}
long long count_rectangles(vector<vector<int>> a)
{
int n = (int) a.size();
int m = (int) a[0].size();
pot_row.resize(n);
pot_col.resize(m);
for (int i = 0; i < n; i++)
{
pot_row[i] = potential(a[i]);
}
for (int j = 0; j < m; j++)
{
vector<int> b;
for (int i = 0; i < n; i++)
{
b.push_back(a[i][j]);
}
pot_col[j] = potential(b);
}
vector<vector<vector<int>>> who_row(m);
for (int i = 0; i < m; i++)
{
who_row[i].resize(m, {});
}
for (int i = 0; i < n; i++)
{
for (auto &it : pot_row[i])
{
int c1 = it.first;
int c2 = it.second;
who_row[c1][c2].push_back(i);
}
}
ll sol = 0;
for (int c1 = 0; c1 < m; c1++)
{
for (int c2 = c1; c2 < m; c2++)
{
vector<int> rows = who_row[c1][c2];
set<int> goods;
if (rows.empty())
{
continue;
}
int i = 0;
while (i < (int) rows.size())
{
int j = i;
while (j + 1 < (int) rows.size() && rows[j + 1] == rows[j] + 1)
{
j++;
}
for (int k = i; k <= j; k++)
{
for (int k2 = k; k2 <= j; k2++)
{
int r1 = rows[k];
int r2 = rows[k2];
bool good = 1;
for (int c = c1; c <= c2; c++)
{
if (has(c, r1, r2) == 0)
{
good = 0;
break;
}
}
if (good)
{
sol++;
}
}
}
i = j + 1;
}
}
}
return sol;
for (int c1 = 0; c1 < m; c1++)
{
for (int c2 = c1; c2 < m; c2++)
{
cout << "on " << c1 << " and " << c2 << " : ";
for (auto &i : who_row[c1][c2])
{
cout << i << " ";
}
cout << "\n";
}
cout << "\n";
}
return 0;
}
