Submission #831181

#	Time	Username	Problem	Language	Result	Execution time	Memory
831181		grogu	Garden (JOI23_garden)	C++14	0 / 100	321 ms	78344 KiB

garden

#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;
}
struct node{
    ll pref,suf,sum,len,mx;
    node(){
        mx = -1;
    }
};

node t[2*maxn];
ll ls[2*maxn],rs[2*maxn],tsz = 0,root = 0;
void init(ll&v,ll tl,ll tr){
    if(!v) v = ++tsz;
    t[v].sum = 0;
    t[v].pref = t[v].suf = t[v].len = t[v].mx = tr-tl+1;
    if(tl==tr){
        return;
    }
    ll mid = (tl+tr)/2;
    init(ls[v],tl,mid);
    init(rs[v],mid+1,tr);
}
node mrg(node l,node r){
    if(r.mx==-1) return l;
    if(l.mx==-1) return r;
    node m;
    m.sum = l.sum + r.sum;
    m.len = l.len + r.len;
    if(l.sum==0) m.pref = l.len+r.pref;
    else m.pref = l.pref;
    if(r.sum==0) m.suf = r.len+l.suf;
    else m.suf = r.suf;
    m.mx = max({l.mx,r.mx,l.suf+r.pref});
    return m;
}
void upd(ll v,ll tl,ll tr,ll i,ll x){
    if(tl==tr){
        t[v].sum+=x;
        if(t[v].sum==0){
            t[v].pref = t[v].suf = 1;
            t[v].sum = 0;
            t[v].mx = 1;
        }else{
            t[v].pref = t[v].suf = 0;
            t[v].sum = 1;
            t[v].mx = 0;
        }
        t[v].len = 1;
        return;
    }
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(ls[v],tl,mid,i,x);
    else upd(rs[v],mid+1,tr,i,x);
    t[v] = mrg(t[ls[v]],t[rs[v]]);
}
node get(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r||tl>tr||l>tr||r<tl) return node();
    if(tl>=l&&tr<=r) return t[v];
    ll mid = (tl+tr)/2;
    return mrg(get(ls[v],tl,mid,l,r),get(rs[v],mid+1,tr,l,r));
}
vector<ll> vx[maxn];
ll ps2x[maxn];
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m >> d;
    init(root,1,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]++;
        upd(root,1,d,y,1);
    }
    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);
        upd(root,1,d,y,1);
    }
    ll uk = n+m;
    for(ll i = 1;i<=2*d;i++){
        psx[i]+=psx[i-1];
        ps2x[i]+=ps2x[i-1];
        psy[i]+=psy[i-1];
    }
    //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<=d;i++){
        for(ll j = i;j<=min(i+d-1,2*d);j++){
            for(ll x : vx[j]) upd(root,1,d,x,-1);
            node m = t[root];
            ll cur = m.mx;
            if(m.sum!=0) cur = max(cur,m.pref+m.suf);
            if(ps2x[j]-ps2x[i-1]==n) ans = min(ans,(d-cur)*(j-i+1));
        }
        for(ll j = i;j<=min(i+d-1,2*d);j++){
            for(ll x : vx[j]) upd(root,1,d,x,1);
        }
    }
    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:131:8: warning: unused variable 'uk' [-Wunused-variable]
  131 |     ll uk = n+m;
      |        ^~

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