| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 273924 | ne4eHbKa | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define _ <<' '<<
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vv;
namespace solution {
const int N = 2505;
int n, m;
list<int> l[N][N], u[N][N];
int p[N], length[N], la[N];
map<int, int> fl[N];
vector<bool> mk;
int get(map<int, int> &a, int b) {
const auto f = a.find(b);
if(f == a.end()) return 0;
return f->sd;
}
ll solve() {
ll ans = 0;
map<int, int> cl, fu, cu;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < m; ++j) {
swap(cl, fl[j]);
for(const int &t : l[i][j])
fl[j][t] = get(cl, t) + 1;
cl.clear();
swap(cu, fu);
for(const int &t : u[i][j])
fu[t] = get(cu, t) + 1;
cu.clear();
for(const auto &a : fl[j]) {
for(const auto &b : fu) {
if(a.ft <= b.sd && b.ft <= a.sd)
++ans;
}
}
}
fu.clear();
}
return ans;
}
int last(int i) {
return la[i] == i ? i : la[i] = last(la[i]);
}
void unite(int i, int j) {
i = last(i), j = last(j);
length[j] += length[i];
la[i] = j;
}
}
ll count_rectangles(vv &a) {
using namespace solution;
n = a.size();
m = a[0].size();
for(int i = 0; i < n; ++i) {
iota(p, p + m, 0);
iota(la, la + m, 0);
mk.assign(m, false);
sort(p, p + m, [&] (const int &fi, const int &se) {return a[i][fi] < a[i][se];});
for(int t = 0; t < m; ) {
int v = a[i][p[t]];
list<int> f;
for(; t < m && a[i][p[t]] == v; ++t) {
int j = p[t];
mk[j] = true;
length[j] = 1;
f.push_back(j);
if(j + 1 < m && mk[j + 1]) unite(j, j + 1);
if(j && mk[j - 1]) unite(j - 1, j);
}
for(int i : f) mk[last(i)] = false;
for(int j : f) {
j = last(j);
if(mk[j]) continue;
mk[j] = true;
if(i == 0 || i == n - 1) continue;
if(j == m - 1 || length[j] == j + 1) continue;
l[i][j].push_back(length[j]);
}
}
}
for(int j = 0; j < m; ++j) {
iota(p, p + n, 0);
iota(la, la + n, 0);
mk.assign(n, false);
sort(p, p + n, [&] (const int &fi, const int &se) {return a[fi][j] < a[se][j];});
for(int t = 0; t < n; ) {
int v = a[p[t]][j];
list<int> f;
for(; t < n && a[p[t]][j] == v; ++t) {
int i = p[t];
mk[i] = true;
length[i] = 1;
f.push_back(i);
if(i + 1 < n && mk[i + 1]) unite(i, i + 1);
if(i && mk[i - 1]) unite(i - 1, i);
}
for(int j : f) mk[last(j)] = false;
for(int i : f) {
i = last(i);
if(mk[i]) continue;
mk[i] = true;
if(j == 0 || j == m - 1) continue;
if(i == n - 1 || length[i] == i + 1) continue;
u[i][j].push_back(length[i]);
}
}
}
return solve();
}
#undef ft
#undef sd
#undef _