이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
typedef pair<int, int> i2;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
long long count_rectangles(vvi A) {
int n = SZ(A), m = SZ(A[0]);
vvvi C(n, vvi(m));
auto fun = [](vector<int> a) {
vector<i2> ans;
int s = SZ(a);
vector<int> p(s), l(s, -1), r(s, -1);
for (int i = 0; i < s; ++i) p[i] = i;
sort(p.begin(), p.end(), [&](int i, int j) { return a[i] < a[j]; });
for (int i : p) {
i2 x = {i, i};
if (i > 0 && l[i - 1] != -1) x.fi = l[i - 1];
if (i + 1 < s && r[i + 1] != -1) x.se = r[i + 1];
if (x.fi > 0 && x.se + 1 < s && min(a[x.fi - 1], a[x.se + 1]) > a[i]) {
ans.push_back(x);
}
r[x.fi] = x.se;
l[x.se] = x.fi;
}
return ans;
};
for (int j = 0; j < m; ++j) {
vector<int> col(n);
for (int i = 0; i < n; ++i) col[i] = A[i][j];
auto pp = fun(col);
for (auto& [i1, i2] : pp) {
C[i2][j].push_back(i1);
}
}
ll ans = 0;
vvi L(n, vi(m, -2));
for (int i = 0; i < n; ++i) {
vector<int> p(m), l(m, -1), r(m, -1);
for (int j = 0; j < m; ++j) p[j] = j;
sort(p.begin(), p.end(), [&](int l, int r) -> bool { return A[i][l] < A[i][r]; });
vector<set<int>> S(m);
for (int j : p) {
i2 x = {j, j};
set<int> cur(ALL(C[i][j]));
set<int> del;
auto inspect = [&](set<int>& s) {
for (int c : cur)
if (!s.count(c))
del.insert(c);
};
if (j > 0 && l[j - 1] != -1) {
x.fi = l[j - 1];
inspect(S[x.fi]);
}
if (j + 1 < m && r[j + 1] != -1) {
x.se = r[j + 1];
inspect(S[l[x.se]]);
}
for (int x : del) cur.erase(x);
if (x.fi > 0 && x.se + 1 < m && min(A[i][x.fi - 1], A[i][x.se + 1]) > A[i][j]) {
if (i - L[x.fi][x.se] > 1) {
L[x.fi][x.se] = i;
}
for (int i1 : cur) {
if (i1 >= L[x.fi][x.se]) {
ans++;
}
}
}
r[x.fi] = x.se;
l[x.se] = x.fi;
S[x.fi] = cur;
}
}
return ans;
}
# | 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... |