# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1274157 | trandangquang | Garden (JOI23_garden) | C++20 | 0 ms | 0 KiB |
{
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';
}