Submission #965151

#	Time	Username	Problem	Language	Result	Execution time	Memory
965151		weakweakweak	Garden (JOI23_garden)	C++17	0 / 100	4 ms	1372 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 () {
        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);
        sty.add(a[i].sc);
    }
    for (int i = 0; i < m; i++) {
        cin >> b[i].fs >> b[i].sc;
        sty.add(b[i].sc);
    }
    ans = min(ans, stx.query() * sty.query());

    sort(b, b + m);
    for (int i = 0; i < m; i++) b[i + m] = b[i];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            stx.add(b[i + j].fs);
            sty.del(b[i + j].sc);
            ans = min(ans, stx.query() * sty.query());
        }
        for (int j = 0; j < m; j++) {
            stx.del(b[i + j].fs);
            sty.add(b[i + j].sc);
        }
    }

    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