Submission #815346

#	Time	Username	Problem	Language	Result	Execution time	Memory
815346		1075508020060209tc	Garden (JOI23_garden)	C++14	30 / 100	3069 ms	46484 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;
int dll[500005];
int nxt[500005];
int nv[500005];
int pv[500005];
int prv[500005];
vector<int>ear[10010];
vector<int>ebr[10010];

int mxgap;
vector<pair<int,int>>vc;
void build(){


mxgap=0;
for(int i=1;i<=n+m;i++){
    int id=vc[i].second;
    int x=vc[i].first;
    int id2=vc[i+1].second;
    int x2=vc[i+1].first;
    if(i==n+m){id2=vc[1].second;}
    nxt[id]=id2;
    prv[id2]=id;
    nv[id]=x2-x;
    pv[id2]=x2-x;
    mxgap=max(mxgap,x2-x);
}
}

void delv(int nw){
int nnw=nxt[nw];
int nnv=nv[nw];
int pnw=prv[nw];
int ppv=pv[nw];
mxgap=max(mxgap,nnv+ppv);
prv[nnw]=pnw;
nxt[pnw]=nnw;
pv[nnw]=nnv+ppv;
nv[pnw]=nnv+ppv;
}

void solve(int tp){
set<int>sqtyp;
for(int i=1;i<=n;i++){
    sqtyp.insert(i);
}
build();
for(int i=tp;i>=tp-D+1;i--){
    for(int j=0;j<ear[i].size();j++){
        sqtyp.erase(ear[i][j]);
    }
    for(int j=0;j<ebr[i].size();j++){
        int v=ebr[i][j];
        v+=n;
        delv(v);
    }
    if(sqtyp.size()==0){
        ans=min(ans,(tp-i+1)*(D-mxgap+1));
    }
}
}



bool cmp(pair<int,int>i,pair<int,int>j){
if(i.second<j.second){return 1;}
return 0;
}

int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);

cin>>n>>m>>D;
ans=D*D;
for(int i=1;i<=n;i++){
    cin>>ar[i].first>>ar[i].second;
    ar[i].first%=D;ar[i].second%=D;
}
for(int i=1;i<=m;i++){
    cin>>br[i].first>>br[i].second;
    br[i].first%=D;
    br[i].second%=D;
}
sort(ar+1,ar+n+1,cmp);
sort(br+1,br+m+1,cmp);
for(int i=1;i<=n;i++){
    ear[ar[i].first].push_back(i);
    ear[ar[i].first+D].push_back(i);
}
for(int i=1;i<=m;i++){
    ebr[br[i].first].push_back(i);
    ebr[br[i].first+D].push_back(i);
}

for(int i=1;i<=n;i++){
    vc.push_back({ar[i].second,i});
}
for(int i=1;i<=m;i++){
    vc.push_back({br[i].second,i+n});
}
sort(vc.begin(),vc.end());
vc.insert(vc.begin()+0,{0,0});
vc.push_back(vc[1]);
vc[n+m+1].first+=D;
for(int tp=D+D-1;tp>=D;tp--){
    solve(tp);
}
cout<<ans<<endl;

}

Compilation message (stderr)

garden.cpp: In function 'void solve(int)':
garden.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0;j<ear[i].size();j++){
      |                 ~^~~~~~~~~~~~~~
garden.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int j=0;j<ebr[i].size();j++){
      |                 ~^~~~~~~~~~~~~~

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