Submission #831159

#TimeUsernameProblemLanguageResultExecution timeMemory
831159groguGarden (JOI23_garden)C++14
0 / 100
3061 ms97876 KiB
#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; vector<pll> vx; vector<pll> vy; 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]++; vx.pb({x,i}); vx.pb({x+d,i}); vy.pb({y,i}); vy.pb({y+d,i}); } 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.pb({x,n+i}); vx.pb({x+d,n+i}); vy.pb({y,n+i}); vy.pb({y+d,n+i}); } 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; sort(all(vx)); sort(all(vy)); ll j = 0; for(ll i = 0;i<si(vx);i++){ pll p = vx[i]; if(p.fi>d) break; while(vx[j].fi<d+p.fi) j++; j--; ll x1 = p.fi,x2 = vx[j].fi; ll l = 1,r = d,mid,rez = -1; while(l<=r){ mid = (l+r)/2; bool ok = 0; for(ll y1 = 1;y1<=d;y1++){ if(sum(x1,y1,x2,y1+mid-1)>=n+m) ok = 1; } if(ok){ rez = mid; r = mid-1; }else l = mid+1; } if(rez!=-1){ ans = min(ans,rez*(x2-x1+1)); //cerr<<x1<< " "<<x2<<" "<<rez<<endl; } } j = 0; for(ll i = 0;i<si(vx);i++){ pll p = vy[i]; if(p.fi>d) break; while(vy[j].fi<d+p.fi) j++; j--; ll y1 = p.fi,y2 = vy[j].fi; ll l = 1,r = d,mid,rez = -1; while(l<=r){ mid = (l+r)/2; bool ok = 0; for(ll x1 = 1;x1<=d;x1++){ if(sum(x1,y1,x1+mid-1,y2)>=n+m) ok = 1; } if(ok){ rez = mid; r = mid-1; }else l = mid+1; } if(rez!=-1){ ans = min(ans,rez*(y2-y1+1)); //cerr<<x1<< " "<<x2<<" "<<rez<<endl; } } 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 **/

Compilation message (stderr)

garden.cpp: In function 'int main()':
garden.cpp:73:8: warning: unused variable 'uk' [-Wunused-variable]
   73 |     ll uk = n+m;
      |        ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...