제출 #815366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815366		1075508020060209tc	Garden (JOI23_garden)	C++14	0 / 100	2318 ms	25696 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 tmxgap;
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);
}
}
stack<vector<int>>stk;
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);
vector<int>vv;
vv={nnw,prv[nnw],pnw,nxt[pnw],pv[nnw],nv[pnw]};
prv[nnw]=pnw;
nxt[pnw]=nnw;
pv[nnw]=nnv+ppv;
nv[pnw]=nnv+ppv;
}
void rev(){
vector<int>vv=stk.top();
prv[vv[0]]=vv[1];
prv[vv[2]]=vv[3];
pv[vv[0]]=vv[4];
nv[vv[2]]=vv[5];
stk.pop();
}

int tbl[500005];
void solve(int tp){
//set<int>sqtyp;
for(int i=1;i<=n;i++){
   tbl[i]=1;
}
int sz=n;
//build();
mxgap=tmxgap;
for(int i=tp;i>=tp-D+1;i--){
    for(int j=0;j<ear[i].size();j++){
        tbl[ear[i][j]]--;
        if(tbl[ear[i][j]]==0){sz--;}
    }
    for(int j=0;j<ebr[i].size();j++){
        int v=ebr[i][j];
        v+=n;
        delv(v);
    }
    if(sz==0){
        ans=min(ans,(tp-i+1)*(D-mxgap+1));
    }
}
while(stk.size()){
    rev();
}
}



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;
mxgap=0;
build();
for(int tp=D+D-1;tp>=D;tp--){
    solve(tp);
}
cout<<ans<<endl;

}

컴파일 시 표준 에러 (stderr) 메시지

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

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