#include <bits/stdc++.h>
using namespace std;
const int di[] = {1, -1, 0, 0};
const int dj[] = {0, 0, 1, -1};
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];
}
}
const int L = 17;
vector<vector<vector<vector<int>>>> st(n, vector<vector<vector<int>>>(m, vector<vector<int>>(L, vector<int>(L))));
vector<int> logs(max(n, m) + 1);
for (int i = 2; i <= max(n, m); i++) {
logs[i] = logs[i >> 1] + 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
st[i][j][0][0] = a[i][j];
}
}
for (int k = 1; k < L; k++) {
for (int i = 0; i + (1 << k) <= n; i++) {
for (int j = 0; j < m; j++) {
st[i][j][k][0] = max(st[i][j][k - 1][0], st[i + (1 << (k - 1))][j][k - 1][0]);
}
}
}
for (int k = 1; k < L; k++) {
for (int t = 0; t < L; t++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j + (1 << k) <= m; j++) {
st[i][j][t][k] = max(st[i][j][t][k - 1], st[i][j + (1 << (k - 1))][t][k - 1]);
}
}
}
}
auto Query = [&](int x1, int y1, int x2, int y2) {
/* int res = 0;
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
res = max(res, a[i][j]);
}
}
return res; */
int kx = logs[x2 - x1 + 1];
int ky = logs[y2 - y1 + 1];
return max({st[x1][y1][kx][ky], st[x2 - (1 << kx) + 1][y1][kx][ky], st[x1][y2 - (1 << ky) + 1][kx][ky],
st[x2 - (1 << kx) + 1][y2 - (1 << ky) + 1][kx][ky]});
};
vector<vector<vector<long long>>> f(n, vector<vector<long long>>(m, vector<long long>(1 << 4)));
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[i][j][mask] += f[i - 1][j][mask];
}
if (j > 0) {
f[i][j][mask] += f[i][j - 1][mask];
}
if (i > 0 && j > 0) {
f[i][j][mask] -= f[i - 1][j - 1][mask];
}
f[i][j][mask] -= a[i][j];
int mx = 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]);
}
}
}
f[i][j][mask] += mx;
}
}
}
auto GetSum = [&](int x1, int y1, int x2, int y2, int mask) {
if (x1 > x2 || y1 > y2) {
return 0LL;
}
long long res = f[x2][y2][mask];
if (x1 > 0) {
res -= f[x1 - 1][y2][mask];
}
if (y1 > 0) {
res -= f[x2][y1 - 1][mask];
}
if (x1 > 0 && y1 > 0) {
res += f[x1 - 1][y1 - 1][mask];
}
return res;
};
int res = 0;
for (int x1 = 0; x1 < n; x1++) {
for (int y1 = 0; y1 < m; y1++) {
for (int x2 = x1; x2 < n; x2++) {
for (int y2 = y1; y2 < m; y2++) {
if (x1 == x2 && y1 == y2) {
res += 1;
continue;
}
auto Valid = [&](int x, int y) {
return x1 <= x && x <= x2 && y1 <= y && y <= y2;
};
long long s = 0;
int mx = Query(x1, y1, x2, y2);
if (x1 == x2) {
{
s += GetSum(x1, y1, x1, y1, 1 << 2);
}
{
s += GetSum(x1, y2, x1, y2, 1 << 3);
}
if (y1 + 1 < y2) {
s += GetSum(x1, y1 + 1, x1, y2 - 1, (1 << 2) + (1 << 3));
}
} else if (y1 == y2) {
{
s += GetSum(x1, y1, x1, y1, 1 << 0);
}
{
s += GetSum(x1, y2, x1, y2, 1 << 1);
}
if (x1 + 1 < x2) {
s += GetSum(x1 + 1, y1, x2 - 1, y1, (1 << 0) + (1 << 1));
}
} else {
{
s += GetSum(x1, y1, x1, y1, (1 << 0) + (1 << 2));
}
{
s += GetSum(x1, y2, x1, y2, (1 << 0) + (1 << 3));
}
{
s += GetSum(x2, y1, x2, y1, (1 << 1) + (1 << 2));
}
{
s += GetSum(x2, y2, x2, y2, (1 << 1) + (1 << 3));
}
if (x1 + 1 < x2) {
s += GetSum(x1 + 1, y1, x2 - 1, y1, (1 << 0) + (1 << 1) + (1 << 2));
s += GetSum(x1 + 1, y2, x2 - 1, y2, (1 << 0) + (1 << 1) + (1 << 3));
}
if (y1 + 1 < y2) {
s += GetSum(x1, y1 + 1, x1, y2 - 1, (1 << 2) + (1 << 3) + (1 << 0));
s += GetSum(x2, y1 + 1, x2, y2 - 1, (1 << 2) + (1 << 3) + (1 << 1));
}
if (x1 + 1 < x2 && y1 + 1 < y2) {
s += GetSum(x1 + 1, y1 + 1, x2 - 1, y2 - 1, (1 << 0) + (1 << 1) + (1 << 2) + (1 << 3));
}
}
if (s == -mx) {
res += 1;
}
}
}
}
}
cout << res << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:112:16: warning: variable 'Valid' set but not used [-Wunused-but-set-variable]
112 | auto Valid = [&](int x, int y) {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Execution timed out |
5091 ms |
177004 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
