Submission #1215075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215075		byunjaewoo	Garden (JOI23_garden)	C++20	21 / 100	399 ms	39924 KiB

garden

#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]), 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=(i>0)*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=(i>0)*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;
}

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