Submission #814404

#	Time	Username	Problem	Language	Result	Execution time	Memory
814404		tranxuanbach	Garden (JOI23_garden)	C++17	100 / 100	754 ms	43160 KiB

garden

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

const int N = 5e5 + 5, D = 5e3 + 5, D2 = D * 2;

struct point{
    int x, y;
};

int n, m, d;
vector <point> a, b;

int ax[D2];
bool ay[D2];
bool bxy[D][D];
int bx[D2];

int ans;
vi ev[N];

struct cyclic_set{
    int l[D], r[D];
    int front;
    int max_dist;

    void init(){
        fill(l, l + D, -1);
        fill(r, r + D, -1);
        front = -1;
        max_dist = 0;
    }

    void push_back(int x){
        if (front == -1){
            l[x] = x;
            r[x] = x;
            front = x;
            return;
        }
        int y = x - 1;
        while (l[y] == -1){
            y--;
        }
        r[y] = x;
        l[x] = y;
        r[x] = front;
        l[front] = x;
    }

    void cal_max_dist(){
        max_dist = (front == -1 ? d : 0);
        For(i, 0, D){
            if (l[i] == -1){
                continue;
            }
            max_dist = max(max_dist, i - l[i] - 1 + (l[i] >= i ? d : 0));
        }
    }

    void erase(int x){
        if (l[x] == x and r[x] == x){
            l[x] = -1;
            r[x] = -1;
            max_dist = d;
            return;
        }
        int lx = l[x], rx = r[x];
        r[lx] = rx;
        l[rx] = lx;
        l[x] = -1;
        r[x] = -1;
        max_dist = max(max_dist, rx - lx - 1 + (lx >= rx ? d : 0));
    }

    int minimum_cover_interval(){
        return d - max_dist;
    }
} stt;

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    cin >> n >> m >> d;
    a.resize(n);
    For(i, 0, n){
        cin >> a[i].x >> a[i].y;
    }
    b.resize(m);
    For(i, 0, m){
        cin >> b[i].x >> b[i].y;
    }

    fill(ax, ax + d, -1);
    fill(ay, ay + d, false);
    for (auto [x, y]: a){
        ax[0] = max(ax[0], x);
        if (x + 1 < d){
            ax[x + 1] = max(ax[x + 1], x + d);
        }
        ay[y] = true;
    }
    For(x, 1, d){
        ax[x] = max(ax[x], ax[x - 1]);
    }
    
    fill(bx, bx + d, -1);
    for (auto [x, y]: b){
        bxy[x][y] = true;
        bx[y] = max(bx[y], x);
    }

    ans = d * d;
    For(l, 0, d){
        For(r, l, l + d){
            ev[r].clear();
        }
        For(y, 0, d){
            if (not ay[y] and bx[y] != -1){
                ev[bx[y]].emplace_back(y);
            }
        }
        stt.init();
        For(y, 0, d){
            if (ay[y] or bx[y] != -1){
                stt.push_back(y);
            }
        }
        stt.cal_max_dist();
        For(r, l, l + d){
            for (auto y: ev[r]){
                stt.erase(y);
            }
            if (r >= ax[l]){
                ans = min(ans, (r - l + 1) * max(1, stt.minimum_cover_interval()));
            }
        }
        For(y, 0, d){
            if (bxy[l][y]){
                bx[y] = l + d;
            }
        }
    }
    cout << ans << "\n";
}

/*
==================================================+
INPUT                                             |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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