#include "rect.h"
#include <vector>
#include <iostream>
#include <set>
#include <stack>
using namespace std;
#define v vector
#define pii pair<int,int>
#define fi first
#define se second
struct gPair{
int l, u;//lower and upper vals
int rc;//row or column
};
long long count_rectangles(std::vector<std::vector<int> > a) {
long long out=0;
int R=a.size();
int C=a[0].size();
//start by getting good pairs
v<gPair> rpairs;
for(int r=1;r<R-1;r++){
v<int> left(C,-1);
v<int> right(C,-1);
stack<int> s;
for(int c=0;c<C;c++){
while(s.size()>0 && a[r][s.top()]<=a[r][c]) s.pop();//go back till reach cell to left with greater than cur
if(s.size()>0) left[c] = s.top();//if cell to left exists then take
s.push(c);
}
s=stack<int>();
for(int c=C-1;c>=0;c--){
while(s.size()>0 && a[r][s.top()]<=a[r][c]) s.pop();//go forward till reach cell to right with greater than cur
if(s.size()>0) right[c] = s.top();//if cell to right exists then take
s.push(c);
}
for(int c=0;c<C;c++){
if(left[c]!=-1 && right[c]!=-1){
rpairs.push_back({left[c],right[c],r});
}
}
}
v<gPair> cpairs;
for(int c=1;c<C-1;c++){
v<int> low(R,-1);
v<int> high(R,-1);
stack<int> s;
for(int r=0;r<R;r++){
while(s.size()>0 && a[s.top()][c]<=a[r][c]) s.pop();//go lower till reach cell lower (up) with greater than cur
if(s.size()>0) low[r] = s.top();//if cell lower exists then take
s.push(r);
}
s=stack<int>();
for(int r=R-1;r>=0;r--){
while(s.size()>0 && a[s.top()][c]<=a[r][c]) s.pop();//go higher till reach cell higher with greater than cur
if(s.size()>0) high[r] = s.top();//if cell higher exists then take
s.push(r);
}
for(int r=0;r<R;r++){
if(low[r]!=-1 && high[r]!=-1){
cpairs.push_back({low[r],high[r],c});
}
}
}
//pairs are now initialized
v<v<set<int>>> rows(R,v<set<int>>(C));
v<v<set<int>>> cols(R,v<set<int>>(C));
for(gPair g:rpairs){
//cout<<g.rc<<" "<<g.l<<" "<<g.u<<endl;
cols[g.rc][g.l+1].insert(g.u-1);//the different columns ahead this cell can get to
}
//cout<<endl;
for(gPair g:cpairs){
//cout<<g.rc<<" "<<g.l<<" "<<g.u<<endl;
rows[g.l+1][g.rc].insert(g.u-1);//the differenc rows ahead this cell can get to
}
//check rows and cols ahead
/**
for(int r=0;r<R;r++){
for(int c=0;c<C;c++){
cout<<r<<" "<<c<<":"<<endl;
for(int it : rows[r][c]){
cout<<it<<" ";
}
cout<<endl;
for(int it : cols[r][c]){
cout<<it<<" ";
}
cout<<endl;
}
}**/
//now try every cell as top left:
for(int r=1;r<R-1;r++){
for(int c=1;c<C-1;c++){
for(int rr:rows[r][c]){
for(int cc:cols[r][c]){
//cout<<r<<" "<<c<<" "<<rr<<" "<<cc<<endl;
bool works=true;
for(int x=r;x<=rr;x++){
//for each along left side check if the far col is = cc
if(cols[x][c].find(cc)==cols[x][c].end()){
works=false;
break;
}
}
for(int x=c;x<=cc;x++){
//for each along left side check if the far col is = cc
if(rows[r][x].find(rr)==rows[r][x].end() || !works){
works=false;
break;
}
}
if(works){
out++;
}
}
}
}
}
return out;
}
