#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define all(a) begin(a), end(a)
#define sz(a) ((int) (a).size())
using ll = long long;
using ld = long double;
const int INF = 1e7 + 1;
const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};
vector<vector<ll>> get_prefs(const vector<vector<int>> &a) {
int n = sz(a), m = sz(a[0]);
vector<vector<ll>> p(n, vector<ll>(m));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
p[i][j] = a[i][j];
if (i != 0) p[i][j] += p[i - 1][j];
if (j != 0) p[i][j] += p[i][j - 1];
if (i != 0 && j != 0) p[i][j] -= p[i - 1][j - 1];
}
}
return p;
}
ll get_sum(int i1, int j1, int i2, int j2, const vector<vector<ll>> &p) {
if (i1 > i2 || j1 > j2) return 0;
ll res = p[i2][j2];
if (i1 != 0) res -= p[i1 - 1][j2];
if (j1 != 0) res -= p[i2][j1 - 1];
if (i1 != 0 && j1 != 0) res += p[i1 - 1][j1 - 1];
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int h, w;
cin >> h >> w;
vector a(h, vector<int>(w));
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
cin >> a[i][j];
}
}
ll ans = h * w;
for (int i = 0; i < h; ++i) {
int len = 0;
for (int j = 1; j < w; ++j) {
++len;
if (j == w - 1 || (a[i][j + 1] < a[i][j]) != (a[i][j] < a[i][j - 1])) {
ans += 1ll * len * (len + 1) / 2;
len = 0;
}
}
}
for (int j = 0; j < w; ++j) {
int len = 0;
for (int i = 1; i < h; ++i) {
++len;
if (i == h - 1 || (a[i + 1][j] < a[i][j]) != (a[i][j] < a[i - 1][j])) {
ans += 1ll * len * (len + 1) / 2;
len = 0;
}
}
}
vector d(1 << 4, vector<vector<int>>(h, vector<int>(w, 0)));
vector c(1 << 4, vector<vector<int>>(h, vector<int>(w, 0)));
for (int t = 0; t < (1 << 4); ++t) {
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
int mn = INF;
for (int k = 0; k < 4; ++k) {
if (!((t >> k) & 1)) continue;
int ii = i + di[k], jj = j + dj[k];
if (ii < 0 || ii >= h || jj < 0 || jj >= w) continue;
if (a[ii][jj] > a[i][j]) mn = min(mn, a[ii][jj]);
}
if (mn == INF) {
c[t][i][j] = 1;
d[t][i][j] = 0;
} else {
c[t][i][j] = 0;
d[t][i][j] = mn - a[i][j];
}
}
}
}
vector<vector<vector<ll>>> pd(1 << 4);
vector<vector<vector<ll>>> pc(1 << 4);
for (int t = 0; t < (1 << 4); ++t) {
pd[t] = get_prefs(d[t]);
pc[t] = get_prefs(c[t]);
}
for (int j1 = 0; j1 < w; ++j1) {
vector<int> rmin(h, INF), rmax(h, 0);
for (int i = 0; i < h; ++i) {
rmin[i] = a[i][j1];
rmax[i] = a[i][j1];
}
for (int j2 = j1 + 1; j2 < w; ++j2) {
for (int i = 0; i < h; ++i) {
rmin[i] = min(rmin[i], a[i][j2]);
rmax[i] = max(rmax[i], a[i][j2]);
}
for (int i1 = 0; i1 < h; ++i1) {
int cmin = rmin[i1], cmax = rmax[i1];
for (int i2 = i1 + 1; i2 < h; ++i2) {
cmin = min(cmin, rmin[i2]);
cmax = max(cmax, rmax[i2]);
ll sumd = get_sum(i1 + 1, j1 + 1, i2 - 1, j2 - 1, pd[(1 << 4) - 1]);
sumd += get_sum(i1, j1 + 1, i1, j2 - 1, pd[(1 << 4) - 1 - (1 << 0)]);
sumd += get_sum(i1 + 1, j2, i2 - 1, j2, pd[(1 << 4) - 1 - (1 << 1)]);
sumd += get_sum(i2, j1 + 1, i2, j2 - 1, pd[(1 << 4) - 1 - (1 << 2)]);
sumd += get_sum(i1 + 1, j1, i2 - 1, j2, pd[(1 << 4) - 1 - (1 << 3)]);
sumd += d[(1 << 4) - (1 << 0) - (1 << 3)][i1][j1];
sumd += d[(1 << 4) - (1 << 0) - (1 << 1)][i1][j2];
sumd += d[(1 << 4) - (1 << 1) - (1 << 2)][i2][j2];
sumd += d[(1 << 4) - (1 << 2) - (1 << 3)][i2][j1];
ll sumc = get_sum(i1 + 1, j1 + 1, i2 - 1, j2 - 1, pc[(1 << 4) - 1]);
sumc += get_sum(i1, j1 + 1, i1, j2 - 1, pc[(1 << 4) - 1 - (1 << 0)]);
sumc += get_sum(i1 + 1, j2, i2 - 1, j2, pc[(1 << 4) - 1 - (1 << 1)]);
sumc += get_sum(i2, j1 + 1, i2, j2 - 1, pc[(1 << 4) - 1 - (1 << 2)]);
sumc += get_sum(i1 + 1, j1, i2 - 1, j2, pc[(1 << 4) - 1 - (1 << 3)]);
sumc += c[(1 << 4) - (1 << 0) - (1 << 3)][i1][j1];
sumc += c[(1 << 4) - (1 << 0) - (1 << 1)][i1][j2];
sumc += c[(1 << 4) - (1 << 1) - (1 << 2)][i2][j2];
sumc += c[(1 << 4) - (1 << 2) - (1 << 3)][i2][j1];
if (sumc == 1 && sumd == cmax - cmin) {
++ans;
}
}
}
}
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Execution timed out |
5048 ms |
20476 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
