This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
#define maxn 10005
ll d;
ll n,m;
ll ps[maxn][maxn];
ll psx[maxn];
ll psy[maxn];
ll sum(ll x,ll y,ll X,ll Y){
ll cur = ps[X][Y]-ps[X][y-1]-ps[x-1][Y]+ps[x-1][y-1];
ll curx = psx[X]-psx[x-1];
ll cury = psy[Y]-psy[y-1];
//if(curx+cury+cur>=n+m) cerr<<curx<< " "<<cury<< " "<<cur<<endl;
//cerr<<x<< " "<<y<< " "<<X<<" "<<Y<<" "<<cur<<endl;
return cur+curx+cury;
}
ll dsu[maxn];
ll sz[maxn];
ll root(ll x){
while(x!=dsu[x]){
x = dsu[x];
}
return x;
}
vector<pair<pll,ll> > upds;
ll curmx = 0;
void upd(ll x,ll y){
x = root(x); y = root(y);
if(x==y) return;
if(sz[x]<sz[y]) swap(x,y);
dsu[y] = x;
sz[x]+=sz[y];
upds.pb({{x,y},curmx});
curmx = max(curmx,sz[x]);
}
void del(){
if(si(upds)==0) return;
pll p = upds.back().fi;
ll mx = upds.back().sc;
upds.popb();
if(p.sc==0){
sz[p.fi] = 0;
return;
}
curmx = mx;
ll x = p.fi,y = p.sc;
sz[x]-=sz[y];
dsu[y] = y;
}
vector<ll> vx[maxn];
ll cnt[maxn];
ll ps2x[maxn];
int main(){
freopen("1.txt","r",stdin);
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> m >> d;
for(ll i = 1;i<=n;i++){
ll x,y; cin >> x >> y;
x++;
y++;
ps[x][y]++;
ps[x+d][y]++;
ps[x][y+d]++;
ps[x+d][y+d]++;
ps2x[x]++;
ps2x[x+d]++;
cnt[y]++;
}
for(ll i = 1;i<=m;i++){
ll x,y; cin >> x >> y;
x++;
y++;
ps[x][y]--;
ps[x+d][y]--;
ps[x][y+d]--;
ps[x+d][y+d]--;
psx[x]++;
psx[x+d]++;
psy[y]++;
psy[y+d]++;
vx[x].pb(y);
vx[x+d].pb(y);
cnt[y]++;
}
for(ll i = 1;i<=2*d;i++){
psx[i]+=psx[i-1];
ps2x[i]+=ps2x[i-1];
psy[i]+=psy[i-1];
}
iota(dsu+1,dsu+1+d,1);
fill(sz+1,sz+1+d,1);
for(ll i = 1;i<=d;i++) if(cnt[i]!=0) sz[i] = 0;
for(ll i = 1;i<d;i++){
if(cnt[i]==0&&cnt[i+1]==0) upd(i,i+1);
}
if(cnt[1]==cnt[d]&&cnt[1]==0) upd(1,d);
for(ll i = 1;i<=d;i++) curmx = max(curmx,sz[i]);
//here; for(ll i = 1;i<=2*d;i++) ceri(ps[i],1,2*d);
for(ll i = 1;i<=2*d;i++){
for(ll j = 1;j<=2*d;j++){
ps[i][j]+=ps[i-1][j]+ps[i][j-1]-ps[i-1][j-1];
}
}
//here; for(ll i = 1;i<=2*d;i++) ceri(ps[i],1,2*d);
ll ans = d*d;
for(ll i = 1;i<=2*d;i++){
upds.clear();
for(ll j = i;j<=min(i+d-1,2*d);j++){
for(ll x : vx[j]){
cnt[x]--;
if(cnt[x]==0){
ll l = x-1; if(l==0) l = d;
ll r = x+1; if(r==d+1) r = 1;
sz[x] = 1;
upds.pb({{x,0},curmx});
curmx = max(sz[x],curmx);
if(cnt[l]==0&&cnt[x]==0) upd(l,x);
if(cnt[r]==0&&cnt[x]==0) upd(r,x);
}
}
if(ps2x[j]-ps2x[i-1]==n) ans = min(ans,(d-curmx)*(j-i+1));
}
while(si(upds)) del();
for(ll j = i;j<=min(i+d-1,2*d);j++){
for(ll x : vx[j]) cnt[x]++;
}
}
cout<<ans<<endl;
return (0-0);
}
/**
2 1 5
1 4
2 2
0 0
3 4 100
20 26
81 56
20 3
58 71
74 82
95 61
95 61
5 7 5000
1046 365
4122 1166
4009 2896
1815 4065
4372 1651
2382 123
1475 836
3313 4005
2579 568
4300 4867
1050 3214
3589 4653
**/
Compilation message (stderr)
garden.cpp: In function 'int main()':
garden.cpp:75:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | freopen("1.txt","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
# | 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... |