제출 #831127

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831127		grogu	Garden (JOI23_garden)	C++14	6 / 100	3080 ms	392020 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;
}
int main(){
	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]++;
    }
    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]++;
    }
    ll uk = n+m;
    for(ll i = 1;i<=2*d;i++){
        psx[i]+=psx[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<=2*d;i++){
        for(ll j = 1;j<=2*d;j++){
            ll l = 1,r = min({d,2*d-i+1,2*d-j+1}),mid,rez = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(sum(i,j,i+mid-1,j+mid-1)>=n+m){
                    rez = mid;
                    r = mid-1;
                }else l = mid+1;
            }
            if(rez==-1) continue;
            ll mn = rez;
            l = 1,r = mn,mid,rez = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(sum(i,j,i+mn-1,j+mid-1)>=n+m){
                    rez = mid;
                    r = mid-1;
                }else l = mid+1;
            }
            if(rez!=-1){
                if(mn*rez<ans){
                    //cerr<<i<< " "<<j<< " "<<i+mn-1<< " "<<j+rez-1<<endl;
                    //cerr<<sum(i,j,i+mn-1,j+rez-1)<<endl;
                }
                ans = min(ans,mn*rez);
            }
            l = 1,r = mn,mid,rez = -1;
            while(l<=r){
                mid = (l+r)/2;
                if(sum(i,j,i+mid-1,j+mn-1)>=n+m){
                    rez = mid;
                    r = mid-1;
                }else l = mid+1;
            }
            if(rez!=-1){
                if(mn*rez<ans){
                    //cerr<<i<< " "<<j<< " "<<i+rez-1<< " "<<j+mn-1<<endl;
                    //cerr<<sum(i,j,i+rez-1,j+mn-1)<<endl;
                }
                ans = min(ans,mn*rez);
            }
        }
    }
    cout<<ans<<endl;
	return (0-0);
}
/**
2 1 5
1 4
2 2
0 0
**/

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

garden.cpp: In function 'int main()':
garden.cpp:88:37: warning: right operand of comma operator has no effect [-Wunused-value]
   88 |             l = 1,r = mn,mid,rez = -1;
      |                                     ^
garden.cpp:103:37: warning: right operand of comma operator has no effect [-Wunused-value]
  103 |             l = 1,r = mn,mid,rez = -1;
      |                                     ^
garden.cpp:63:8: warning: unused variable 'uk' [-Wunused-variable]
   63 |     ll uk = n+m;
      |        ^~

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