#include <bits/stdc++.h>
using namespace std;
const int inf = (int) 1.001e9;
const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};
vector<vector<long long>> f[1 << 4];
long long GetSum(int x1, int y1, int x2, int y2, int mask) {
if (x1 > x2 || y1 > y2) {
return 0LL;
}
long long res = f[mask][x2][y2];
if (x1 > 0) {
res -= f[mask][x1 - 1][y2];
}
if (y1 > 0) {
res -= f[mask][x2][y1 - 1];
}
if (x1 > 0 && y1 > 0) {
res += f[mask][x1 - 1][y1 - 1];
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
if (n < m) {
vector<vector<int>> b(m, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[j][i] = a[i][j];
}
}
a = b;
swap(n, m);
}
for (int mask = 0; mask < (1 << 4); mask++) {
f[mask] = vector<vector<long long>>(n, vector<long long>(m));
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int mask = 0; mask < (1 << 4); mask++) {
if (i > 0) {
f[mask][i][j] += f[mask][i - 1][j];
}
if (j > 0) {
f[mask][i][j] += f[mask][i][j - 1];
}
if (i > 0 && j > 0) {
f[mask][i][j] -= f[mask][i - 1][j - 1];
}
f[mask][i][j] -= a[i][j];
int mx = 0;
int cnt = 0;
for (int d = 0; d < 4; d++) {
if (mask >> d & 1) {
int ni = i + di[d];
int nj = j + dj[d];
if (0 <= ni && ni < n && 0 <= nj && nj < m && a[ni][nj] < a[i][j]) {
mx = max(mx, a[ni][nj]);
}
if (0 <= ni && ni < n && 0 <= nj && nj < m && a[ni][nj] > a[i][j]) {
cnt += 1;
}
}
}
if (cnt == 0) {
mx += inf + a[i][j];
}
f[mask][i][j] += mx;
}
}
}
long long res = n * m;
for (int x = 0; x < n; x++) {
map<long long, int> cnt;
for (int y = 0; y < m; y++) {
if (y > 0) {
res += cnt[-(GetSum(x, y, x, y, 1 << 3) - inf + GetSum(x, 0, x, y - 1, (1 << 2) + (1 << 3)))];
}
cnt[GetSum(x, y, x, y, 1 << 2) - GetSum(x, 0, x, y, (1 << 2) + (1 << 3))] += 1;
}
}
for (int l = 0; l < n; l++) {
for (int r = l + 1; r < n; r++) {
map<long long, int> cnt;
for (int i = 0; i < m; i++) {
if (i > 0) {
res += cnt[-(-inf + GetSum(l, i, l, i, (1 << 0) + (1 << 3)) + GetSum(r, i, r, i, (1 << 1) + (1 << 3)) + GetSum(l + 1, i, r - 1, i, (1 << 0) + (1 << 1) + (1 << 3)) + GetSum(l + 1, 0, r - 1, i - 1, (1 << 0) + (1 << 1) + (1 << 2) + (1 << 3))
+ GetSum(l, 0, l, i - 1, (1 << 0) + (1 << 2) + (1 << 3)) + GetSum(r, 0, r, i - 1, (1 << 1) + (1 << 2) + (1 << 3)))];
}
cnt[GetSum(l, i, l, i, (1 << 0) + (1 << 2)) + GetSum(r, i, r, i, (1 << 1) + (1 << 2)) + GetSum(l + 1, i, r - 1, i, (1 << 0) + (1 << 1) + (1 << 2)) - GetSum(l + 1, 0, r - 1, i, (1 << 0) + (1 << 1) + (1 << 2) + (1 << 3))
- GetSum(l, 0, l, i, (1 << 0) + (1 << 2) + (1 << 3)) - GetSum(r, 0, r, i, (1 << 1) + (1 << 2) + (1 << 3))] += 1;
}
}
}
cout << res << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
5097 ms |
47272 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
