이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
vector<pair<ii, ii> > get_linii(vector<vi> &a) {
int n = int(a.size()), m = int(a[0].size());
vector<set<ii> > Perechi(n);
for(int i = 1; i + 1 < n; ++i) {
vector<ii> ord;
for(int j = 0; j < m; ++j)
ord.push_back({a[i][j], j});
sort(ord.rbegin(), ord.rend());
set<int> Poz;
int p2 = 0;
for(int j = 0; j < m; ++j) {
auto [v, p] = ord[j];
while(p2 < m && ord[p2].first == v) {
Poz.insert(ord[p2].second);
++p2;
}
if(1) {
auto it = Poz.lower_bound(p);
++it;
if(it != Poz.end()) {
if(*it > p + 1)
Perechi[i].insert(ii{p, *it});
}
}
if(1) {
auto it = Poz.lower_bound(p);
if(it != Poz.begin()) {
--it;
if(p > *it + 1)
Perechi[i].insert(ii{*it, p});
}
}
}
}
vector<pair<ii, ii> > Re;
for(int i = 0; i < n; ++i) {
for(auto it : Perechi[i]) {
int p = i;
while(p + 1 < n && Perechi[p + 1].count(it)) ++p;
Re.push_back({{i - 1, p + 1}, it});
for(int j = i + 1; j <= p; ++j)
Perechi[j].erase(it);
}
}
return Re;
}
struct AIB2D {
int n, m;
vector<vi> V;
AIB2D(int N, int M) : n(N + 1), m(M + 1), V(N + 1, vi(M + 1, 0)) {}
void update(int l, int c, int v) {
++l; ++c;
while (l < n) {
int p = c;
while (p < m) {
V[l][p] += v;
p += p & -p;
}
l += l & -l;
}
}
int query(int l, int c) {
++l; ++c;
int re = 0;
while (l) {
int p = c;
while (p) {
re += V[l][p];
p -= p & -p;
}
l -= l & -l;
}
return re;
}
};
ll count_rectangles(vector<vi> a) {
int n = int(a.size()), m = int(a[0].size());
vector<vi> b(m, vi(n, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
b[j][i] = a[i][j];
auto V = get_linii(a), H = get_linii(b);
for(auto &[x, y] : H) swap(x, y);
auto inclus = [&](ii a, ii b) {
///b inclus in a
return b.first >= a.first && b.second <= a.second;
};
int re = 0;
vector< vector<vector<ii> > > LinV(n, vector(m, vector<ii>()));
auto LinH = LinV;
for(auto [x, y] : V) {
for(int i = x.first; i <= x.second; ++i) {
LinV[i][y.second].push_back({i - x.first, y.second - y.first});
}
}
for(auto [x, y] : H) {
for(int j = y.first; j <= y.second; ++j) {
LinH[x.second][j].push_back({x.second - x.first, j - y.first});
}
}
AIB2D Sol(n, m);
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
for(auto [xh, yh] : LinH[i][j]) {
Sol.update(xh, m - yh - 1, 1);
}
for(auto [xv, yv] : LinV[i][j]) {
int v = Sol.query(xv, m - yv - 1);
if(v) {
re += v;
}
}
for(auto [xh, yh] : LinH[i][j]) {
Sol.update(xh, m - yh - 1, -1);
}
}
}
return re;
}
컴파일 시 표준 에러 (stderr) 메시지
rect.cpp: In function 'll count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:98:10: warning: variable 'inclus' set but not used [-Wunused-but-set-variable]
98 | auto inclus = [&](ii a, ii b) {
| ^~~~~~
# | 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... |