#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
vector<vector<int>>matrix, nxtBigR, nxtBigUp, temp;
struct cuad{
int ddH, htH, midH, midW, ddW, htW;
int value;
pair<int, int>pos;
cuad *LU, *LD, *RU, *RD; // si es linea horizontal, solo LD, RD,
// linea Vertical, LU, LD.
bool hor, ver;
cuad(int lH, int rH, int lW, int rW){
ddH = lH;
htH = rH;
ddW = lW;
htW = rW;
midH = (ddH + htH)/2;
midW = (ddW + htW)/2;
hor = ddH == htH;
ver = ddW == htW;
if(ddH != htH or ddW != htW){
if(hor and ! ver){
LD = new cuad(ddH, htH, ddW, midW);
RD = new cuad(ddH, htH, midW+1, htW);
if(LD->value > RD->value){
value = LD->value;
pos = LD->pos;
}else{
value = RD->value;
pos = RD->pos;
}
}else if(ver and !hor){
LD = new cuad(ddH, midH, ddW, htW);
LU = new cuad(midH + 1, htH, ddW, htW);
if(LD->value > LU->value){
value = LD->value;
pos = LD->pos;
}else{
value = LU->value;
pos = LU->pos;
}
}else{
LD = new cuad(ddH, midH, ddW, midW);
RU = new cuad(midH+1, htH, midW+1, htW);
LU = new cuad(midH+1, htH, ddW, midW);
RD = new cuad(ddH, midH, midW +1, htW);
value = max(LD->value, RD->value);
value = max(value, max(RU->value, LU->value));
if(LD->value == value){
pos = LD->pos;
}else if(RU->value == value){
pos = RU->pos;
}else if(LU->value == value){
pos = LU->pos;
}else{
pos = RD->pos;
}
}
}else{
value = temp[ddH][ddW];
pos = {ddH, ddW};
}
}
pair<int, pair<int, int > > query(int lH, int rH, int lW, int rW){
if(lH == ddH and rH == htH and lW == ddW and rW == htW)return {value, pos};
if(rH <= midH and rW <= midW){
return LD->query(lH, rH, lW, rW);
}
if(lH > midH and lW > midH){
return RU ->query(lH, rH, lW, rW);
}
if(rH<=midH and lW > midH){
return RD ->query(lH, rH, lW, rW);
}
if(lH > midH and rW <= midW){
return LU ->query(lH, rH, lW, rW);
}
if(rH <= midH){
return max(LD ->query(lH, rH, lW, midW), RD ->query(lH, rH, midW+1, rW));
}else if( lH > midH){
return max(LU ->query(lH, rH, lW, midW), RU ->query(lH, rH, midW+1, rW));
}
if(rW <= midW){
return max(LD ->query(lH, midH, lW, rW), LU ->query(midH+1, rH, lW, rW));
}else if( lW > midW){
return max(RD ->query(lH, midH, lW, rW), RU ->query(midH+1, rH, lW, rW));
}
return max(max(LD->query(lH, midH, lW, midW), RD->query(lH, midH, midW+1, rW)), max(LU->query(midH+1, htH, lW, midH), RU->query(midH+1, rH, midW+1, rW)));
}
};
cuad *grandeR, *grandeU, *matris, *grandeL, *grandeD;
int N, M;
long long count_rectangles(std::vector<std::vector<int> > a) {
N = a.size();
M = a[0].size();
matrix = a;
ll ans = 0;
for(int i = 1 ; i < N-1 ; i ++){
for(int j = 1 ; j < M-1 ; j ++){
for(int ii = i ; ii < N-1 ; ii++){
for(int jj = j ; jj < M-1 ; jj++){
bool valid = true;
for(int x = i ; x <= ii ; x ++){
for(int pp = j ; pp <= jj ; pp ++){
int val = matrix[x][pp];
if(!(val < matrix[x][j-1] and val < matrix[x][jj+1] and val < matrix[i-1][pp] and val < matrix[ii +1][pp])){
pp = jj +1;
x = ii + 1;
valid = false;
}
}
}
if(valid)ans ++;
}
}
}
}
return ans;
}
