Submission #965195

#	Time	Username	Problem	Language	Result	Execution time	Memory
965195		weakweakweak	Garden (JOI23_garden)	C++17	30 / 100	3033 ms	1320 KiB

garden

//被嗆，憑什麼卡我常數
#include <bits/stdc++.h>
using namespace std;
using pii = pair<short, short>;
 
#pragma GCC optimize("O3")

#define fs first
#define sc second
 
int n, m, d;
 
struct special_set {
    set<short> sts;
    multiset<int> mst;
    short cnt[5010] = {0};
    inline int query () {
        if (mst.empty ()) return 1;
        int z = *mst.rbegin();
        z = max(z, *sts.begin() + d - *sts.rbegin());
        return d - z + 1;
    }    
    inline void add (int x) {
        if (x >= d) return;
        cnt[x]++;
        if (cnt[x] != 1) return;
        auto it = sts.insert(x).first;
        auto nextit = next(it);
        bool y1 = (nextit != sts.end());
        bool y2 = (it != sts.begin());
        auto previt = it;
        if (y2) previt = prev(it);
        if (y1 and y2) mst.erase(mst.find(*nextit - *previt));
        if (y1) mst.insert(*nextit - x);
        if (y2) mst.insert(x - *previt);
    }
    inline void del (int x) {
        if (x >= d) return;
        cnt[x]--;
        if (cnt[x] != 0) return;
        auto it = sts.find(x);
        auto nextit = next(it);
        bool y1 = (nextit != sts.end());
        bool y2 = (it != sts.begin());
        auto previt = it;
        if (y2) previt = prev(it);
        if (y1 and y2) mst.insert(*nextit - *previt);
        if (y1) mst.erase(mst.find(*nextit - x));
        if (y2) mst.erase(mst.find(x - *previt));
        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++) {
        if (i % 2 == 0) {
            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());
            }
            stx.del(b[i].fs);
            sty.add(b[i].sc);
        }
        else {
            stx.add(b[i + m - 1].fs);
            sty.del(b[i + m - 1].sc);
            ans = min(ans, stx.query() * sty.query());
            for (int j = m - 1; j >= 0; j--) {
                stx.del(b[i + j].fs);
                sty.add(b[i + j].sc);
                ans = min(ans, stx.query() * sty.query());
            }
        }
    }
 
    cout << ans << '\n';
return 0;}

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