#include <bits/stdc++.h>
using namespace std;
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
using ii = pair<int, int>;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
ll count_rectangles(vector<vi> a) {
int n = sz(a), m = sz(a[0]);
vector<vi> l(n, vi(m)), r(n, vi(m));
vector<vi> d(n, vi(m)), u(n, vi(m));
forn(i, n) forn(j, m) {
int k = j - 1;
while (k >= 0 && a[i][k] < a[i][j]) k = l[i][k];
l[i][j] = k;
}
forn(i, n) dforn(j, m) {
int k = j + 1;
while (k < m && a[i][k] < a[i][j]) k = r[i][k];
r[i][j] = k;
}
forn(i, m) forn(j, n) {
int k = j - 1;
while (k >= 0 && a[k][i] < a[j][i]) k = u[k][i];
u[j][i] = k;
}
forn(i, m) dforn(j, n) {
int k = j + 1;
while (k < n && a[k][i] < a[j][i]) k = d[k][i];
d[j][i] = k;
}
vector<tuple<int, int, int, int>> ret;
auto check = [&](int i1, int i2, int j1, int j2) {
if (i1 < 0 || i2 >= n || j1 < 0 || j2 >= m) return;
if (i2 - i1 < 2 || j2 - j1 < 2) return;
forsn(i, i1 + 1, i2) {
if (r[i][j1] <= j2 - 1 || l[i][j2] >= j1 + 1) return;
}
forsn(j, j1 + 1, j2) {
if (d[i1][j] <= i2 - 1 || u[i2][j] >= i1 + 1) return;
}
ret.eb(i1, i2, j1, j2);
};
forsn(i, 1, n - 1) forsn(j, 1, m - 1) {
check(u[i + 1][j], i + 1, j - 1, r[i][j - 1]);
check(u[i + 1][j], i + 1, l[i][j + 1], j + 1);
check(i - 1, d[i - 1][j], l[i][j + 1], j + 1);
check(i - 1, d[i - 1][j], j - 1, r[i][j - 1]);
check(i - 1, d[i - 1][j], j - 1, r[d[i - 1][j] - 1][j - 1]);
check(i - 1, d[i - 1][j], l[d[i - 1][j] - 1][j + 1], j + 1);
}
sort(all(ret));
return unique(all(ret)) - begin(ret);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |