#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
struct rect{
int x1, y1, x2, y2;
bool operator<(const rect &other) const {
if (x1 != other.x1) return x1 < other.x1;
if (y1 != other.y1) return y1 < other.y1;
if (x2 != other.x2) return x2 < other.x2;
if (y2 != other.y2) return y2 < other.y2;
return false;
}
};
using bs = bitset<700>;
ll count_rectangles(vvi a) {
int n = a.size(), m = a[0].size();
vvi gr(n, vi(m, m)), lr(n, vi(m, -1)), gc(n, vi(m, n)), lc(n, vi(m, -1));
for (int i = 0; i < n; i++) {
vi st1, st2;
for (int j = 0; j < m; j++) {
while (!st1.empty() && a[i][j] >= a[i][st1.back()]) {
gr[i][st1.back()] = j;
st1.pop_back();
}
st1.push_back(j);
}
for (int j = m-1; j >= 0; j--) {
while (!st2.empty() && a[i][j] >= a[i][st2.back()]) {
lr[i][st2.back()] = j;
st2.pop_back();
}
st2.push_back(j);
}
}
for (int j = 0; j < m; j++) {
vi st1, st2;
for (int i = 0; i < n; i++) {
while (!st1.empty() && a[i][j] >= a[st1.back()][j]) {
gc[st1.back()][j] = i;
st1.pop_back();
}
st1.push_back(i);
}
for (int i = n-1; i >= 0; i--) {
while (!st2.empty() && a[i][j] >= a[st2.back()][j]) {
lc[st2.back()][j] = i;
st2.pop_back();
}
st2.push_back(i);
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cout << gr[i][j] << " ";
// }
// cout << "\n";
// }
// cout << "\n";
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// cout << gr[i][j] << " ";
// }
// cout << "\n";
// }
set<rect> valid;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
int x = gr[i][j-1], y = gc[i-1][j], z = lr[i][j+1], w = lc[i+1][j];
if (x<m && y<n) { // top-left corner
bool good = (x > j) && (y > i);
for (int k = j; k < x; k++) {
good = good && ((gc[i-1][k] == y) || (lc[y][k] == i-1));
}
for (int k = i; k < y; k++) {
good = good && ((gr[k][j-1] == x) || (lr[k][x] == i-1));
}
if (good) valid.insert(rect{i, j, x-1, y-1});
}
if (z >= 0 && y < n) { // top-right corner
bool good = (z < j) && (y > i);
for (int k = z+1; k <= j; k++) {
good = good && ((gc[i-1][k] == y) || (lc[y][k] == i-1));
}
for (int k = i; k < y; k++) {
good = good && ((lr[k][j+1] == z) || (gr[k][z] == j+1));
}
if (good) valid.insert(rect{z+1, j, i, y-1});
}
if (x < m && w >= 0) { // bottom-left corner
bool good = (x > i) && (w < i);
for (int k = j; k < x; k++) {
good = good && ((lc[i+1][k] == w) || (gc[w][k] == i+1));
}
for (int k = w+1; k <= i; k++) {
good = good && ((gr[k][j-1] == x) || (lr[k][x] == i-1));
}
if (good) valid.insert(rect{i, w+1, x-1, j});
}
if (z >= 0 && w >= 0) { // bottom-right corner
bool good = (z < j) && (w < i);
for (int k = z+1; k <= j; k++) {
good = good && ((lc[i+1][k] == w) || (gc[w][k] == i+1));
}
for (int k = w+1; k <= i; k++) {
good = good && ((lr[k][j+1] == z) || (gr[k][z] == j+1));
}
if (good) valid.insert(rect{z+1, w+1, i, j});
}
}
}
// for (auto &el : valid) {
// cout << "(" << el.x1 << "," << el.y1 << ") -> " << "(" << el.x2 << "," << el.y2 << ")\n";
// }
return valid.size();
}
