제출 #1215112

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1215112		byunjaewoo	Garden (JOI23_garden)	C++20	30 / 100	3094 ms	12976 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], t[D];
bool chk[D];
multiset<int> st, diff;
vector<int> cy, vec[D], rvec[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];
        chk[a[i]]=true, cy.push_back(b[i]);
    }
    for(int i=1; i<=m; i++) {
        cin>>c[i]>>d_[i];
        vec[c[i]].push_back(d_[i]), rvec[d_[i]].push_back(c[i]);
    }
    sort(cy.begin(), cy.end()), cy.erase(unique(cy.begin(), cy.end()), cy.end());
    for(int i=0; i<d; i++) {
        sort(vec[i].begin(), vec[i].end());
        if(vec[i].empty()) t[i]=-1;
        else t[i]=vec[i].back();
    }
    for(int i=0, j=0; i<d; i++) {
        int mr=d*(j>0)+cy[(j+cy.size()-1)%cy.size()];
        vector<pair<int, int>> tmp;
        for(int k=0; k<d; k++) if(!chk[k]) tmp.push_back({t[k], k});
        sort(tmp.begin(), tmp.end());
        st.clear(), diff.clear();
        for(int k=0; k<d; k++) add(k);
        ans=min(ans, (mr-i+1)*qry());
        for(auto [v, k]:tmp) {
            del(k);
            ans=min(ans, (max(mr, v)-i+1)*qry());
        }
        for(int k:rvec[i]) t[k]=d+i;
        if(j<cy.size() && i==cy[j]) j++;
    }
    cout<<ans;
    return 0;
}

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