Submission #965148

#	Time	Username	Problem	Language	Result	Execution time	Memory
965148		weakweakweak	Garden (JOI23_garden)	C++17	0 / 100	161 ms	1368 KiB

garden

//target : 60pts
//希望我沒假解
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

#pragma GCC optimize("Ofast")
#define fs first
#define sc second

int n, m, d;

struct special_set {
    set<int> sts;
    multiset<int> mst;
    int cnt[10010] = {0};
    int query () {
        if (mst.empty()) return d;
        else {
            int z = *mst.rbegin();
            z = max(z, *sts.begin() + d - *sts.rbegin());
            return d - z + 1;
        }
    }    
    void add (int x) {
        cnt[x]++;
        if (sts.find(x) != sts.end() or cnt[x] > 1) return;
        auto zz = sts.insert(x);
        auto it = zz.first;
        if (next(it) != sts.end() and it != sts.begin()) mst.erase(mst.find(*next(it) - *prev(it)));
        if (next(it) != sts.end()) mst.insert(*next(it) - x);
        if (it != sts.begin()) mst.insert(x - *prev(it));
    }
    void del (int x) {
        cnt[x]--;
        auto it = sts.find(x);
        if (it == sts.end() or cnt[x] > 0) return;
        if (next(it) != sts.end() and it != sts.begin()) mst.insert(*next(it) - *prev(it));
        if (next(it) != sts.end()) mst.erase(mst.find(*next(it) - x));
        if (it != sts.begin()) mst.erase(mst.find(x - *prev(it)));
        sts.erase(it);
    }
}stx, sty;

pii a[5010], b[10010];
int ans = INT_MAX;

int main () {
    ios_base :: sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> d;
    for (int i = 0; i < n; i++) {
        cin >> a[i].fs >> a[i].sc;
        stx.add(a[i].fs);
        // stx.add(a[i].fs + d);
        sty.add(a[i].sc);
        // sty.add(a[i].sc + d);
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i].fs >> b[i].sc;
        sty.add(b[i].sc);
        // sty.add(b[i].sc + d);
    }
    ans = min(ans, stx.query() * sty.query());
    // for (int x : sty.mst) cout << x << ' ';
    // cout << '\n';
    // for (int x : sty.sts) cout << x << ' ';
    // cout << '\n';

    sort(b, b + m);
    for (int i = 0; i < m; i++) b[i + m] = b[i];
    for (int i = 0; i < m; i++) {
        // cout << "!" << ' ' << stx.query() << ' ' << sty.query() << '\n';
        for (int j = 0; j < m; j++) {
            stx.add(b[i + j].fs);
            // stx.add(b[i + j].fs + d);
            sty.del(b[i + j].sc);
            // sty.del(b[i + j].sc + d);
            // cout << i << ' ' << j << ' ' << stx.query() << ' ' << sty.query() << ' ' << stx.query() * sty.query() << '\n';
            ans = min(ans, stx.query() * sty.query());
        }
        for (int j = 0; j < m; j++) {
            stx.del(b[i + j].fs);
            // stx.del(b[i + j].fs + d);
            sty.add(b[i + j].sc);
            // sty.add(b[i + j].sc + d);
        }
    }

    cout << ans << '\n';
return 0;}

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