#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();
/**
bool subSix=true;
for(int i=0;i<R;i++){//check for sub six
for(int j=0;j<C;j++){
if(a[i][j]>1){
subSix=false;
break;
}
}
if(!subSix){
break;
}
}
if(subSix){
//find sub rectangles with dp[i][j] = {min(dp[i-1][j-1].first, dp[i][j-1].first),
// min(dp[i-1][j-1].second, dp[i-1][j].second)}
//then for each rectangle check the border.
//can speed up by making so only consider if dp[i-1][j-1].first and dp[i][j-1].first are equal
v<v<pii>> dp(R,v<pii>(C,{-1,-1}));
for(int r=1;r<R-1;r++){
for(int c=1;c<C-1;c++){
if(a[r][c]==0){
int f=r;
int s=c;
int r1=dp[r-1][c-1].fi;
int r2=dp[r-1][c].fi;
int c1=dp[r-1][c-1].se;
int c2=dp[r][c-1].se;
if(c1==c2 && c1!=-1){
s=max(c1,1);
}
if(r1==r2 && r1!=-1){
f=max(r1,1);
}
if(c1==-1 && c2!=-1){
s=c2;
}
else if(r1==-1 && r2!=-1){
f=r2;
}
dp[r][c]={f,s};
}
}
}
//check dp table
/**for(int r=0;r<R;r++){
for(int c=0;c<C;c++){
cout<<"("<<dp[r][c].fi<<" "<<dp[r][c].se<<") ";
}
cout<<endl;
}**/
//dp table is now made
//iterate from bottom right to top left
//for every distinct dp[i][j] value check borders of that rect then mark as covered
/**
set<pii> checked;
checked.insert({-1,-1});
for(int r=R-1;r>0;r--){
for(int c=C-1;c>0;c--){
if(a[r][c]==0 && checked.find(dp[r][c])==checked.end()){
checked.insert(dp[r][c]);
int r1=dp[r][c].fi;
int c1=dp[r][c].se;
bool works=true;
for(int i=r1;i<=r;i++){
if(a[i][c1-1]==0 || a[i][c+1]==0){
works=false;
break;
}
}
for(int j=c1;j<=c;j++){
if(a[r1-1][j]==0 || a[r+1][j]==0){
works=false;
break;
}
}
if(works){
out++;
}
}
}
}
}
else if((R<=200 && C<=200) || R<=3){//sub one, two, three and five
for(int r1=1;r1<R-1;r1++){
for(int c1=1;c1<C-1;c1++){
for(int r2=r1;r2<R-1;r2++){
for(int c2=c1;c2<C-1;c2++){
//have rect with top left r1, c1, bottom right r2, c2
//check every value of the rect
bool works=true;
for(int r=r1;r<=r2;r++){
for(int c=c1;c<=c2;c++){
if(a[r1-1][c]<=a[r][c]){
works=false;
break;
}
if(a[r2+1][c]<=a[r][c]){
works=false;
break;
}
if(a[r][c1-1]<=a[r][c]){
works=false;
break;
}
if(a[r][c2+1]<=a[r][c]){
works=false;
break;
}
}
if(!works){
break;
}
}
if(works){
out++;
}
}
}
}
}
}**/
if(false){
int xass=0;
xass++;
}
else{
//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;
}
