이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//希望我沒假解...
/*
把題目轉換一下,就變成我有兩個直線,type a就是在兩個直線各加一個點,tybe b就是我可以選哪個直線要加一個點。最後求兩個直線中的相鄰的點對最大的,用d扣掉再+1後就是我要選的範圍。乘起來的最小值就是答案。
我可以枚舉x這條直線上要拿哪個區間,先枚舉左界,然後右界往外長的時候,發現如果[左界, 右界]覆蓋掉所有y值為h的type b,然後不存在y值為h的type a,那我就可以從y這條線上把h丟掉。(dsu 把h - 1、h、h+1 merge起來,但如果h - 1, h + 1我還沒覆蓋到,那就不merge)
維護y這條直線我用有兩種優化的dsu;然後維護h第一次被完全覆蓋掉的位置可用前綴和判斷、用linked list儲存
總時間複雜度就是O(d^2 反阿克曼(2d)) ~= O(d^2)
*/
#include <bits/stdc++.h>
using namespace std;
short n, m, d, cntax[10010] = {0}, cntbx[10010] = {0}, cntb[10010][5010] = {0}, www[5010] = {0}; //www[i]代表i這個y值目前存在哪個x的linked_list裡面,0代表沒存
int ans = INT_MAX;
bool abcovery[10010] = {0};
bool acovery[10010] = {0};
struct linked_list {
int pre[5010], nxt[5010], used[5010] = {0};
void init () {
pre[0] = nxt[0] = 0;
for (int i = 1; i <= d; i++) pre[i] = nxt[i] = -1, used[i] = 0;
}
void add (int x) {
int edd = pre[0];
nxt[x] = nxt[edd], pre[nxt[edd]] = x;
pre[x] = edd, nxt[edd] = x;
used[x] = 1;
}
void del (int x) {
nxt[pre[x]] = nxt[x], pre[nxt[x]] = pre[x];
pre[x] = nxt[x] = -1;
used[x] = 0;
}
} linkl[10010];
struct disjoinit_set{
int fa[10010], b[10010], sz[10010] = {0}, ans = 0;
int find (int x) {return fa[x] == x ? x : fa[x] = find (fa[x]);}
void merge (int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y], fa[y] = fa[x];
ans = max(ans, sz[x]);
}
void init () {
ans = 0;
for (int i = 1; i <= d; i++) {
fa[i] = i, sz[i] = 1;
fa[i + d] = i + d, sz[i + d] = 1;
if (abcovery[i]) b[i] = b[i + d] = 1;
else ans = 1;
}
for (int i = 2; i <= d * 2; i++) {
if (!b[i] and !b[i - 1]) merge (i, i - 1);
}
}
void delb (int x) {
if (!b[x]) return;
b[x] = 0, ans = max(ans, 1);
if (x - 1 != 0 and !b[x - 1]) merge(x, x - 1);
if (x + 1 <= d * 2 and !b[x + 1]) merge(x, x + 1);
}
int query () {return d - ans;}
}ydsu;
int main () {
//初始化
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m >> d;
for (int i = 1, x, y; i <= n; i++) {
cin >> x >> y;
if (x == 0) x += d;
if (y == 0) y += d;
acovery[y] = 1;
abcovery[y] = 1;
cntax[x]++, cntax[x + d]++;
}
for (int i = 1; i <= d * 2; i++) cntax[i] += cntax[i - 1];
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
if (x == 0) x += d;
if (y == 0) y += d;
cntb[x][y]++; cntb[x + d][y]++;
abcovery[y] = 1;
}
for (int x = 1; x <= d * 2; x++) for (int y = 1; y <= d; y++) cntb[x][y] += cntb[x - 1][y];
//初始化linkedlist,看[1, i]能覆蓋到哪,這個i到d
for (int i = 1; i <= d; i++) {
linkl[i].init();
for (int j = 1; j <= d; j++) {
if (!acovery[j] and cntb[i][j] != cntb[i - 1][j] and cntb[i][j] == cntb[d][j]) {
www[j] = i;
linkl[i].add(j);
}
}
}
for (int i = d + 1; i <= d * 2; i++) linkl[i].init();
for (int i = 1; i <= d; i++) {
//處理詢問
ydsu.init();
// cout << ydsu.query() << '\n';
for (int len = 1; len <= d; len++) {
int j = i + len - 1;
int now = linkl[j].nxt[0];
while (now > 0) {
ydsu.delb(now); ydsu.delb(now + d);
now = linkl[j].nxt[now];
}
if ((cntax[j] - cntax[i - 1]) >= n) {
// if (len * ydsu.query() < 8) cout << i << ' ' << j <<' ' << ydsu.query() << '\n';
ans = min(ans, len * ydsu.query());
}
}
//修改linkedlist
if (i == d) break;
for (int j = 1; j <= d; j++) {
//刪掉i帶來的貢獻
if (cntb[i + d][j] - cntb[i][j] != cntb[d][j] and www[j]) {
linkl[www[j]].del(j);
www[j] = 0;
}
//加入i + d + 1帶來的貢獻
if (cntb[i + d + 1][j] - cntb[i][j] == cntb[d][j] and cntb[i + d + 1][j] > cntb[i + d][j] and !www[j]) {
www[j] = i + d + 1;
linkl[www[j]].add(j);
}
}
}
cout << ans << '\n';
}
# | 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... |