제출 #1274152

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1274152		trandangquang	Garden (JOI23_garden)	C++20	0 / 100	61 ms	4268 KiB

garden

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

#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define eb emplace_back
#define _ << " " <<

template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}

const int N=505050;
const int D=5050;

int n,m,d,p[N],q[N],r[N],s[N],res;
bool eyn[D],eym[D];
int nxt[D],prv[D];
int mxDel[D];
int x[D*2];
vector<int> nah[D],del[D*2];

int calc(int y1, int y2){
    if(y1<y2) return y2-y1-1;
    return d-1-y1 + y2;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin>>n>>m>>d;
    rep(i,n) cin>>p[i]>>q[i], eyn[q[i]]=1;
    rep(i,m) cin>>r[i]>>s[i], eym[s[i]]=1;

    rep(i,n){
        maxi(x[0], p[i]);
        maxi(x[p[i]+1], p[i]+d);
    }
    rep(i,2*d){
        if(i>0) maxi(x[i], x[i-1]);
    }

    res=d*d;
    rep(i,m){
        maxi(mxDel[s[i]], r[i]);
        nah[r[i]].eb(s[i]);
    }
    rep(i,d){
        int fst=-1, lst=-1, mxLen=0;
        rep(j,d) if(eyn[j]||eym[j]){
            if(fst!=-1) fst=j;
            if(lst!=-1){
                prv[j]=lst; nxt[lst]=j;
                maxi(mxLen, calc(lst,nxt[lst]));
            }
            lst=j;
        }
        nxt[lst]=fst; prv[fst]=lst;
        maxi(mxLen, calc(lst,nxt[lst]));

        foru(j,i,i+d-1) del[j].clear();
        rep(j,d) if(eym[j]&&!eyn[j]){
            del[mxDel[j]].eb(j);
        }

        foru(j,i,i+d-1){
            for(int y:del[j]){
                nxt[prv[y]]=nxt[y];
                prv[nxt[y]]=prv[y];
                maxi(mxLen, calc(prv[y], nxt[prv[y]]));
            }
            if(j>=x[i]) mini(res, (j-i+1)*(d-mxLen));
//            cout<<i _ j _ d-mxLen<<'\n';
        }

        for(int y:nah[i]){
            maxi(mxDel[y],i+d);
        }
    }

    cout<<res<<'\n';
}

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