Submission #1215134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215134		byunjaewoo	Garden (JOI23_garden)	C++20	75 / 100	3090 ms	10932 KiB

garden

#include <bits/stdc++.h>
using namespace std;

const int Nmax=10010;
int N, M, X, ans=Nmax*Nmax;
vector<int> A[Nmax], B[Nmax], V, all;
int mx, L[Nmax], R[Nmax], C[Nmax];
int mx0, L0[Nmax], R0[Nmax], C0[Nmax];

void Del(int x) {
    if(--C[x]>0) return;
    if(L[x]<R[x]) mx=max(mx, R[x]-L[x]);
    else mx=max(mx, X+R[x]-L[x]);
    R[L[x]]=R[x], L[R[x]]=L[x];
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M>>X;
    for(int i=1; i<=N; i++) {
        int x, y; cin>>x>>y;
        x++, y++;
        A[x].push_back(y), A[x+X].push_back(y);
        all.push_back(y), C0[y]++;
    }
    for(int i=1; i<=M; i++) {
        int x, y; cin>>x>>y;
        x++, y++;
        B[x].push_back(y), B[x+X].push_back(y), V.push_back(y);
        all.push_back(y), C0[y]++;
    }
    sort(all.begin(), all.end()), all.erase(unique(all.begin(), all.end()), all.end());
    for(int i=0; i<all.size(); i++) {
        R0[all[i]]=all[(i+1)%all.size()];
        L0[all[i]]=all[(i+all.size()-1)%all.size()];
        if(all[i]<R0[all[i]]) mx0=max(mx0, R0[all[i]]-all[i]);
        else mx0=max(mx0, X+R0[all[i]]-all[i]);
    }
    for(int l=1; l<=X; l++) {
        mx=mx0;
        for(int i=1; i<=X; i++) L[i]=L0[i], R[i]=R0[i], C[i]=C0[i];
        int flag=0;
        for(int r=l; r<l+X; r++) {
            for(int y:A[r]) flag++;
            for(int y:B[r]) Del(y);
            if(flag==N) ans=min(ans, (r-l+1)*(X-mx+1));
        }
    }
    cout<<ans;
    return 0;
}

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