#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using bs = bitset<700>;
struct rect{
int x1, y1, x2, y2;
rect() {}
rect(int a, int b, int c, int d) {
x1 = min(a, c); x2 = max(a, c);
y1 = min(b, d); y2 = max(b, d);
}
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;
}
};
pair<int, int> rot90(int n, int m, int x, int y) {
return {y, n-x-1};
}
pair<int, int> rotm90(int n, int m, int x, int y, int t) {
for (int i = 0; i < t; i++) {
auto sw = rot90(n, m, x, y);
x = sw.first, y = sw.second;
swap(n, m);
}
return {x, y};
}
vvi rotate(vvi &a) {
int n = a.size(), m = a[0].size();
vvi nw(m, vi(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
auto sw = rot90(n, m, i, j);
nw[sw.first][sw.second] = a[i][j];
}
}
return nw;
}
set<rect> count(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));
// vvi gr(n, vi(m, m-1)), lr(n, vi(m, 0)), gc(n, vi(m, n-1)), lc(n, vi(m, 0));
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++) {
// if (gr[i][j] == m-1 && lr[i][m-1] > j) gr[i][j] = m;
if (gr[i][j] == m) {
gr[i][j]--;
while (lr[i][gr[i][j]] > j) gr[i][j]--;
}
if (gc[i][j] == n) {
gc[i][j]--;
while (lc[gc[i][j]][j] > i) gc[i][j]--;
}
if (lr[i][j] == -1) {
lr[i][j]++;
while (gr[i][lr[i][j]] < j) lr[i][j]++;
}
if (lc[i][j] == -1) {
lc[i][j]++;
while (gc[lc[i][j]][j] < i) lc[i][j]++;
}
}
}
vector<vector<bs>> down(n, vector<bs>(n)), across(m, vector<bs>(m));
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = 0; k < m; k++) {
if (!(gc[i][k] == j || lc[j][k] == i)) continue;
down[i][j].set(k);
}
down[i][j].flip();
}
}
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
for (int k = 0; k < n; k++) {
if (!(gr[k][i] == j || lr[k][j] == i)) continue;
across[i][j].set(k);
}
across[i][j].flip();
}
}
set<rect> valid;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
// for (int i2 = i; i2 < n-1; i2++) {
// bs v = down[i-1][i2+1];
// for (int j2 = j; j2 < m-1; j2++) {
// bs v2 = across[j-1][j2+1];
// if (v._Find_next(j-1) <= j2) continue;
// if (v2._Find_next(i-1) <= i2) continue;
// valid.insert({i, j, i2, j2});
// }
// }
int xo = gr[i][j-1], yo = gc[i-1][j];
int xu = gr[yo-1][j-1], yu = gc[i-1][xo-1];
vector<pair<int, int>> opts({{xo, yo}, {xo, yu}, {xu, yo}, {xu, yu}});
for (auto &[x, y] : opts) {
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] == j-1));
if (good) valid.insert(rect(i, j, y-1, x-1));
}
}
}
}
return valid;
}
ll count_rectangles(vvi a) {
int n = a.size(), m = a[0].size();
vvi gr(n, vi(m, m-1)), lr(n, vi(m, 0)), gc(n, vi(m, n-1)), lc(n, vi(m, 0));
auto valid = count(a);
for (int unrot = 3; unrot >= 1; unrot--) {
vvi nw = rotate(a); swap(a, nw);
swap(n, m);
auto v2 = count(a);
for (auto r : v2) {
auto cl = rotm90(n, m, r.x1, r.y1, unrot);
auto cr = rotm90(n, m, r.x2, r.y2, unrot);
valid.insert(rect(cl.first, cl.second, cr.first, cr.second));
}
}
return valid.size();
}
