Submission #1215071

#TimeUsernameProblemLanguageResultExecution timeMemory
1215071byunjaewooGarden (JOI23_garden)C++20
0 / 100
365 ms39788 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int N=500010, D=5010, INF=1e18; int n, m, d, ans=INF, a[N], b[N], c[N], d_[N]; multiset<int> st, diff; vector<int> cx, cy, vec[D]; void add(int x) { if(st.find(x)!=st.end()) { st.insert(x); return; } auto p=st.upper_bound(x); int l=-1, r=-1; if(p!=st.end()) r=(*p), diff.insert(r-x); if(p!=st.begin()) l=(*prev(p)), diff.insert(x-l); if(l>=0 && r>=0) diff.erase(diff.find(r-l)); st.insert(x); } void del(int x) { st.erase(st.find(x)); if(st.find(x)!=st.end()) return; auto p=st.upper_bound(x); int l=-1, r=-1; if(p!=st.end()) r=(*p), diff.erase(diff.find(r-x)); if(p!=st.begin()) l=(*prev(p)), diff.erase(diff.find(x-l)); if(l>=0 && r>=0) diff.insert(r-l); } int qry() { if(diff.empty()) return (*st.rbegin())-(*st.begin())+1; return min((*st.rbegin())-(*st.begin())+1, d-(*diff.rbegin())+1); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>m>>d; for(int i=1; i<=n; i++) { cin>>a[i]>>b[i]; add(a[i]); cx.push_back(a[i]), cy.push_back(b[i]); } for(int i=1; i<=m; i++) { cin>>c[i]>>d_[i]; add(c[i]); cx.push_back(c[i]), cy.push_back(d_[i]), vec[d_[i]].push_back(c[i]); } sort(cx.begin(), cx.end()), cx.erase(unique(cx.begin(), cx.end()), cx.end()); sort(cy.begin(), cy.end()), cy.erase(unique(cy.begin(), cy.end()), cy.end()); for(int i=cy[0]; i<cy.back(); i++) for(int j:vec[i]) del(j); for(int i=0; i<cy.size(); i++) { int l=cy[i]; for(int r=d+cy[(i+cy.size()-1)%cy.size()]; r<d+cy[i]; r++) { for(int j:vec[r-d]) del(j); ans=min(ans, (r-l+1)*qry()); } if(i==cy.size()-1) break; for(int r=d+cy[(i+cy.size()-1)%cy.size()]; r<d+cy[i]; r++) for(int j:vec[r-d]) add(j); for(int j=cy[i]; j<cy[i+1]; j++) for(int k:vec[j]) add(k); if(i==0) { for(int j=cy.back(); j<d; j++) for(int k:vec[j]) del(k); for(int j=0; j<cy[0]; j++) for(int k:vec[j]) del(k); } else { for(int j=cy[i-1]; j<cy[i]; j++) for(int k:vec[j]) del(k); } } cout<<ans; 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...