제출 #965195

#제출 시각아이디문제언어결과실행 시간메모리
965195weakweakweakGarden (JOI23_garden)C++17
30 / 100
3033 ms1320 KiB
//被嗆,憑什麼卡我常數 #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;}
#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...