제출 #965141

#제출 시각아이디문제언어결과실행 시간메모리
965141weakweakweakGarden (JOI23_garden)C++17
6 / 100
3050 ms1880 KiB
//target : 75pts //希望我沒假解 #include <bits/stdc++.h> using namespace std; using pii = pair<int,int>; #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; return d - *mst.rbegin() + 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;}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...