// In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
using namespace std;
const long long N = 210, OO = 1e12 + 7, M = 1e9 + 7, M2 = 998244353, sq = 360, lg = 23;
typedef pair <int, int> pii;
int bad[N][N][10], n, m, a[N][N], mn[N][N][N];
void get1(int i) {
vector <int> v;
for(int j = 0; j < m; j++) {
while(v.size()) {
if(a[i][v[v.size() - 1]] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][0] = v[v.size() - 1];
v.pb(j);
}
v.clear();
for(int j = m - 1; j >= 0; j--) {
while(v.size()) {
if(a[i][v[v.size() - 1]] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][1] = v[v.size() - 1];
else
bad[i][j][1] = m;
v.pb(j);
}
}
void get2(int j) {
vector <int> v;
for(int i = 0; i < n; i++) {
while(v.size()) {
if(a[v[v.size() - 1]][j] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][2] = v[v.size() - 1];
v.pb(i);
}
v.clear();
for(int i = n - 1; i >= 0; i--) {
while(v.size()) {
if(a[v[v.size() - 1]][j] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][3] = v[v.size() - 1];
else
bad[i][j][3] = n;
v.pb(i);
}
}
int32_t main() {
use_fast;
cin >> n >> m;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
cin >> a[i][j];
for(int i = 0; i < n; i++)
get1(i);
for(int j = 0; j < m; j++)
get2(j);
for(int k = 1; k < m; k++) {
for(int i = 1; i < n; i++) {
mn[k][i][i] = bad[i][k][0];
for(int j = i + 1; j < n - 1; j++)
mn[k][i][j] = max(mn[k][i][j - 1], bad[j][k][0]);
}
}
int ans = 0;
for(int k = 0; k < m - 2; k++) {
for(int i = 1; i < n - 1; i++) {
int mi = OO;
for(int j = i; j < n - 1; j++) {
mi = min(mi, bad[j][k][1]);
int mk = OO, ml = 0;
for(int l = k + 1; l < m - 1; l++) {
mk = min(mk, bad[i - 1][l][3]);
ml = max(ml, bad[j + 1][l][2]);
int mj = mn[l + 1][i][j];
if(mj >= k + 1 || mk <= j || ml >= i || mi <= l)
continue;
ans++;
}
}
}
}
cout << ans << endl;
return 0;
}
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- ...
*/
Compilation message
/tmp/ccCJqwmu.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cctAdYZH.o:rect.cpp:(.text.startup+0x0): first defined here
/tmp/ccCJqwmu.o: In function `main':
grader.cpp:(.text.startup+0x89e): undefined reference to `count_rectangles(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2: error: ld returned 1 exit status
