/*
TC: O(nm^2)
*/
#include "rect.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
ll count_rect_top_left(const vvi& a, int miny, int minx) {
ll ans = 0ll;
int Y = a.size(), X = a[0].size();
int maxy = Y - 2, maxx = X - 2;
vi col_max(maxx - minx + 1, 0);
vi row_max(maxy - miny + 1, 0);
for(int y = miny; y <= maxy; y++) {
for(int i = 0; i + miny <= y; i++) {
row_max[i] = 0;
}
for(int x = minx; x <= maxx; x++) {
col_max[x - minx] = max(col_max[x - minx], a[y][x]);
for(int i = 0; i + miny <= y; i++) {
row_max[i] = max(row_max[i], a[i + miny][x]);
}
// check if valid
bool is_valid = true;
// rows
for(int i = 0; i + miny <= y; i++) {
if(row_max[i] >= a[i + miny][minx - 1] || row_max[i] >= a[i + miny][x + 1]) {
is_valid = false;
break;
}
}
// columns
for(int i = 0; i + minx <= x; i++) {
if(col_max[i] >= a[miny - 1][i + minx] || col_max[i] >= a[y + 1][i + minx]) {
is_valid = false;
break;
}
}
if(is_valid) ans++;
}
}
return ans;
}
ll count_rectangles(vvi a) {
int rows = a.size(), cols = a[0].size();
ll ans = 0ll;
for(ll y = 1ll; y <= rows - 2ll; y++) {
for(ll x = 1ll; x <= cols -2ll; x++) {
ans += count_rect_top_left(a, y, x);
}
}
return ans;
}
