This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n,m,d;
int frx[10000];
int fry[10000];
vector <int> h[10000];
queue <int> pos[5000];
int firstOcc[5000];
vector <int> upd[10000];
struct S
{
int sz=0;
int prv[10000];
int nxt[10000];
int fr[10000]={0};
int minim=2*d;
int maxim=-1;
int ans=0;
S(vector <pair <int,int>> a)
{
sz=(int)a.size()/2;
for(int i=0; i<2*sz; i++)
{
fr[a[i].first]=a[i].second;
if(i>0)
nxt[a[i-1].first]=a[i].first;
if(i+1<2*sz)
{
prv[a[i+1].first]=a[i].first;
ans=max(ans,a[i+1].first-a[i].first-1);
}
minim=min(minim,a[i].first%d);
maxim=max(maxim,a[i].first%d);
}
}
void Rem(int x)
{
if(sz==1)
{
ans=d-1;
return;
}
fr[x]--;
if(fr[x]>0)
return;
if(x>=d)
sz--;
if(sz==1)
{
ans=d-1;
return;
}
if(x==minim)
{
minim=nxt[x];
x+=d;
}
if(x==maxim)
{
maxim=prv[x];
x-=d;
}
ans=max(ans,nxt[x]-prv[x]-1);
prv[nxt[x]]=prv[x];
nxt[prv[x]]=nxt[x];
}
};
int main()
{
cin>>n>>m>>d;
int cntdy=0;
for(int i=1; i<=n; i++)
{
int p,q;
cin>>p>>q;
frx[p]++;
frx[p+d]++;
if(fry[q]==0)
cntdy++;
fry[q]++;
fry[q+d]++;
}
for(int i=1; i<=m; i++)
{
int r,s;
cin>>r>>s;
frx[r]++;
frx[r+d]++;
h[s].push_back(r);
h[s+d].push_back(r);
}
vector <pair <int,int>> aux;
for(int i=0; i<2*d; i++)
if(frx[i]>0)
aux.push_back(make_pair(i,1));
int ans=(int)1e9;
for(int i=0; i<d; i++)
firstOcc[i]=-1;
for(int i=0; i<2*d; i++)
{
for(auto it:h[i])
{
pos[it].push(i);
if(pos[it].front()==i)
firstOcc[it]=i;
if(pos[it].front()==i-d)
{
pos[it].pop();
firstOcc[it]=pos[it].front();
}
}
for(int j=0; j<2*d; j++)
upd[j].clear();
for(int j=0; j<d; j++)
{
if(firstOcc[j]>=0)
{
upd[firstOcc[j]].push_back(j);
upd[firstOcc[j]].push_back(j+d);
}
}
S A(aux);
int cnt=0;
for(int j=i; j>=0; j--)
{
for(int it:upd[j])
A.Rem(it);
if(fry[j]>0)
cnt++;
if(cnt>=cntdy)
ans=min(ans,(i-j+1)*(d-A.ans));
}
}
cout<<ans<<"\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |