Submission #815934

#	Time	Username	Problem	Language	Result	Execution time	Memory
815934		1075508020060209tc	Garden (JOI23_garden)	C++14	100 / 100	671 ms	10124 KiB

garden

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

int n;int m;int D;
pair<int,int>ar[500005];
pair<int,int>br[500005];
int ans;
// double link list
int dll[500005];
int nxt[500005];
int nv[500005];
int pv[500005];
int prv[500005];

void build(){
for(int i=0;i<=D-2;i++){
    nxt[i]=i+1;
    prv[i+1]=i;
}
nxt[D-1]=0;prv[0]=D-1;
for(int i=0;i<=D-1;i++){
    pv[i]=1;nv[i]=1;
}
}


int delv(int nw){
int nnw=nxt[nw];
int nnv=nv[nw];
int pnw=prv[nw];
int ppv=pv[nw];
prv[nnw]=pnw;
nxt[pnw]=nnw;
pv[nnw]=nnv+ppv;
nv[pnw]=nnv+ppv;
return nnv+ppv;
}
// double link list
vector<int>eupd[10100];
set<int>dlcl[10100];
int clmbt[50100];
int hassq[50100];
int typ1[10100];
int least;
void solve(int tp){
build();
int mxgap=1;
for(int i=0;i<D;i++){
    if(!hassq[i]&&clmbt[i]==1000000){
        mxgap=max(mxgap,delv(i));
    }
}
for(int i=tp;i>=tp-D+1;i--){
    for(auto it=dlcl[i].begin();it!=dlcl[i].end();it++){
        int clm=*it;
        if(!hassq[clm]){
            mxgap=max(mxgap,delv(clm));
        }
    }
    if(i<=least){
        ans=min(ans,(D-mxgap+1)*(tp-i+1));
    }
}

}


void upd(int tp){
eupd[tp-D]=eupd[tp];
for(int i=0;i<eupd[tp-D].size();i++){
    int clm=eupd[tp-D][i];
    dlcl[clmbt[clm]].erase(clm);
    clmbt[clm]=tp-D;
    dlcl[clmbt[clm]].insert(clm);
}
if(typ1[tp]){
    least=tp-D;
    typ1[tp-D]=1;
}
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    cin>>n>>m>>D;
    least=D+D-1;
    for(int i=1;i<=n;i++){
        cin>>ar[i].first>>ar[i].second;
        ar[i].first%=D;ar[i].second%=D;
        hassq[ar[i].second]=1;
        least=min(least,ar[i].first+D);
        typ1[ar[i].first+D]=1;
    }

    for(int i=0;i<=D;i++){
        clmbt[i]=1000000;
    }
    for(int i=1;i<=m;i++){
        cin>>br[i].first>>br[i].second;
        br[i].first%=D;br[i].second%=D;
        eupd[br[i].first+D].push_back(br[i].second);
        clmbt[br[i].second]=min(clmbt[br[i].second],br[i].first+D);
    }
    if(D==1){
        cout<<1<<endl;return 0;
    }

    for(int i=0;i<D;i++){
        if(clmbt[i]==1000000){continue;}
        dlcl[clmbt[i]].insert(i);
    }
    ans=D*D;
    for(int tp=D+D-1;tp>=D;tp--){
        build();
        solve(tp);
        upd(tp);
    }
    cout<<ans<<endl;


}

Compilation message (stderr)

garden.cpp: In function 'void upd(int)':
garden.cpp:70:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 | for(int i=0;i<eupd[tp-D].size();i++){
      |             ~^~~~~~~~~~~~~~~~~~

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