// Radewoosh approach, but i found out a solution to solve the problem in O(n * m * min(n, m))
#include <bits/stdc++.h>
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
#define int long long
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef ngu
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int n, m;
cin >> n >> m;
vector<vector<int>> a;
if (n < m) {
a.resize(n + 1, vector<int>(m + 1));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
}
}
} else {
a.resize(m + 1, vector<int>(n + 1));
for (int i = n; i >= 1; --i) {
for (int j = 1; j <= m; ++j) {
cin >> a[j][i];
}
}
swap(n, m);
}
vector<int> value;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
value.emplace_back(a[i][j]);
}
}
sort(value.begin(), value.end());
value.erase(unique(value.begin(), value.end()), value.end());
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
a[i][j] = lower_bound(value.begin(), value.end(), a[i][j]) - value.begin() + 1;
}
}
vector<vector<vector<long long>>> diff(16, vector<vector<long long>>(n + 1, vector<long long>(m + 1)));
auto inside = [&](int i, int j) {
return 1 <= i && i <= n && 1 <= j && j <= m;
};
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int mask = 0; mask < 16; ++mask) {
int mx = 0, mn = n * m + 1;
for (int dr = 0; dr < 4; ++dr) {
if (mask >> dr & 1) {
int x = i + dx[dr];
int y = j + dy[dr];
if (inside(x, y)) {
if (a[x][y] < a[i][j]) {
mx = max(mx, a[x][y]);
} else {
mn = min(mn, a[x][y]);
}
}
}
}
diff[mask][i][j] = mx - a[i][j] + (mn == n * m + 1) * (mn + a[i][j]);
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
for (int mask = 0; mask < 16; ++mask) {
diff[mask][i][j] += diff[mask][i - 1][j];
diff[mask][i][j] += diff[mask][i][j - 1];
diff[mask][i][j] -= diff[mask][i - 1][j - 1];
}
}
}
auto get_rect = [&](int mask, int i, int j, int x, int y) -> long long {
if (i > x || j > y) {
return 0;
}
return diff[mask][x][y] - diff[mask][i - 1][y] - diff[mask][x][j - 1] + diff[mask][i - 1][j - 1];
};
vector<long long> L(m + 1), mid(m + 1), R(m + 1);
auto get = [&](const vector<long long> &v, int l, int r) -> long long {
return l <= r ? v[r] - v[l - 1] : 0;
};
auto count_matches = [&](const vector<pair<long long, int>> &a, const vector<pair<long long, int>> &b) {
int res = 0;
int n = (int) a.size(), m = (int) b.size();
int L = n - 1, R = n - 1;
for (int i = m - 1; i >= 0; --i) {
while (R >= 0 && a[R].first > b[i].first) {
R--;
L = R;
}
while (a[L].first == b[i].first && L - 1 >= 0 && a[L - 1] > b[i]) {
L--;
}
if (L >= 0 && L <= R && a[L].first == a[R].first && a[L].first == b[i].first && a[L].second > b[i].second) {
res += R - L + 1;
}
}
return res;
};
int res = 0;
for (int r1 = 1; r1 <= n; ++r1) {
for (int r2 = r1; r2 <= n; ++r2) {
vector<pair<long long, int>> needs, candidates;
for (int c = 1; c <= m; ++c) {
{ // only column c
if (r1 == r2) {
res++;
} else {
long long sum_dif = 0;
sum_dif += get_rect(4, r1, c, r1, c);
sum_dif += get_rect(1, r2, c, r2, c);
sum_dif += get_rect(5, r1 + 1, c, r2 - 1, c);
res += sum_dif == n * m + 1;
}
}
{ // mid
if (r1 != r2) {
mid[c] = mid[c - 1];
mid[c] += get_rect(14, r1, c, r1, c);
mid[c] += get_rect(15, r1 + 1, c, r2 - 1, c);
mid[c] += get_rect(11, r2, c, r2, c);
} else {
mid[c] = mid[c - 1] + get_rect(10, r1, c, r1, c);
}
}
{ // left
if (r1 != r2) {
L[c] = L[c - 1];
L[c] += get_rect(6, r1, c, r1, c);
L[c] += get_rect(7, r1 + 1, c, r2 - 1, c);
L[c] += get_rect(3, r2, c, r2, c);
} else {
L[c] = L[c - 1] + get_rect(2, r1, c, r1, c);
}
}
{ // right
if (r1 != r2) {
R[c] = R[c - 1];
R[c] += get_rect(12, r1, c, r1, c);
R[c] += get_rect(13, r1 + 1, c, r2 - 1, c);
R[c] += get_rect(9, r2, c, r2, c);
} else {
R[c] = R[c - 1] + get_rect(8, r1, c, r1, c);
}
}
if (c > 1) {
needs.emplace_back(get(R, c, c) + get(mid, 1, c - 1), c);
}
if (c < m) {
candidates.emplace_back(n * m + 1 - get(L, c, c) + get(mid, 1, c), c);
}
}
sort(needs.begin(), needs.end());
sort(candidates.begin(), candidates.end());
res += count_matches(needs, candidates);
}
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
24 ms |
17616 KB |
Output is correct |
| 3 |
Correct |
28 ms |
17228 KB |
Output is correct |
| 4 |
Correct |
26 ms |
17608 KB |
Output is correct |
| 5 |
Correct |
27 ms |
17604 KB |
Output is correct |
| 6 |
Correct |
30 ms |
17616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
