Submission #965641

#	Time	Username	Problem	Language	Result	Execution time	Memory
965641		weakweakweak	Garden (JOI23_garden)	C++17	100 / 100	2110 ms	789948 KiB

garden

//下了測資還是找不到bug...
/*
把題目轉換一下，就變成我有兩個直線，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;
 
int 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();
        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) {
                ans = min(ans, len * ydsu.query());
            }
        }
 
        //修改linkedlist
        if (i == d) break;
        for (int j = 1; j <= d; j++) {
            if (acovery[j]) continue;
            //刪掉i帶來的貢獻    
            if (www[j] and cntb[www[j]][j] - cntb[i][j] < cntb[d][j]) {
                linkl[www[j]].del(j);
                www[j] = 0;
            }
            //加入i + d + 1帶來的貢獻
            if (cntb[i + d][j] - cntb[i][j] == cntb[d][j] and cntb[i + d][j] > cntb[i + d - 1][j] and !www[j]) {
                www[j] = i + d;
                linkl[www[j]].add(j);
                // cout << i + d + 1 << ' ' << j << '\n';
            }
        }
    }
 
    cout << ans << '\n';
}

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25