#include "rect.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vp vector<pi>
void print(vvi &L) {
cerr << "{";
for (auto i : L) {
cerr << "{";
for (auto j : i) cerr << j << ", ";
cerr << "},\n";
}
cerr << endl;
}
void print(vi &L) {
cerr << "{";
for (auto i : L) cerr << i << ", ";
cerr << "}" << endl;
}
ll count_rectangles(vector<vector<int>> B) {
if (B.size() <= 2 || B[0].size() <= 2) return 0;
vvi CL(B.size(), vi(B[0].size(), -1));
vvi CR = CL, RT = CL, RB = CL;
vp L;
for (int j = 0; j < B.size(); j++) {
//cerr << "j : " << j << endl;
L.clear();
for (int i = B[0].size()-1; i > -1; i--) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) CL[j][i] = L.back().second;
else CL[j][i] = B[0].size()-1;
L.push_back({B[j][i], i});
}
}
for (int j = 0; j < B.size(); j++) {
//cerr << "j : " << j << endl;
L.clear();
for (int i = 0; i < B[0].size(); i++) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) CR[j][i] = L.back().second;
else CR[j][i] = 0;
L.push_back({B[j][i], i});
}
}
for (int i = 0; i < B[0].size(); i++) {
//cerr << "j : " << j << endl;
L.clear();
for (int j = B.size()-1; j > -1; j--) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) RT[j][i] = L.back().second;
else RT[j][i] = B.size()-1;
L.push_back({B[j][i], j});
}
}
for (int i = 0; i < B[0].size(); i++) {
//cerr << "j : " << j << endl;
L.clear();
for (int j = 0; j < B.size(); j++) {
//cerr << "i : " << i << endl;
while (L.size() && L.back().first < B[j][i]) L.pop_back();
;
//cerr << "oink" << endl;
if (L.size()) RB[j][i] = L.back().second;
else RB[j][i] = 0;
L.push_back({B[j][i], j});
}
}
//*
cerr << "CL\n";
print(CL);
cerr << "CR\n";
print(CR);
cerr << "RT\n";
print(RT);
cerr << "RB\n";
print(RB);
//*/
ll t = 0;
/*
for (int i = 0; i < B.size(); i++) {
for (int j = 0; j < B[0].size(); j++) {
//t += (B[i][j]);
}
}//*/
for (int c1 = 0; c1 < B.size(); c1++) {
for (int c2 = c1+2; c2 < B.size(); c2++) {
cerr << "\n" << "c1 : " << c1 << ", c2 : " << c2 << ", t : " << t << endl;
vi L(B[0].size(), 0);
for (int r1 = 0; r1 < B[0].size(); r1++) {
L[r1] = (RT[c1][r1] >= c2 && RB[c2][r1] <= c1);
}
cerr << c1 << " " << c2 << " : ";
print(L);
for (int r1 = 0; r1 < B[0].size(); r1++) {
if (!L[r1+1]) continue;
for (int r2 = r1+2; r2 < B[0].size(); r2++) {
if (!L[r2-1]) break;
//cerr << "oink" << endl;
bool q = 0;
for (int c = c1+1; c < c2; c++) {
if (CL[c][r1] >= r2 && CR[c][r2] <= r1) continue;
q = 1;
break;
}
t += !q;
}
}
}
}
return t;
}
