제출 #965258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965258		weakweakweak	Garden (JOI23_garden)	C++17	0 / 100	3087 ms	2396 KiB

garden

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

#define fs first
#define sc second
 
short 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[501000], b[1000010];
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());
 
    for (int i = 0; i < (1 << m); i++) {
        for (int j = 0; j < m; j++) if ((1 << j) & i) {
            sty.del(b[j].sc);
            stx.add(b[j].fs);
        }
        ans = min(ans, stx.query() * sty.query());
        for (int j = 0; j < m; j++) if ((1 << j) & i) {
            sty.add(b[j].sc);
            stx.del(b[j].fs);
        }
    }
 
    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