JOI 春合宿 2008 Day 3 Origami
問題文はちゃんと読みましょう
Origami,簡単だけど5ではないでしょ…
— おくら (@okuraofvegetabl) 2015, 2月 22
ええええええええええ辺の長さ20cm以下とか聞いてないぞおおおおお
— おくら (@okuraofvegetabl) 2015, 2月 22
mapで数えるだけの問題を2次元座圧+2次元imosでやりました。
普通にやったらMLEするので、平面走査風にやってメモリ節約しました。
int imos[10050],cnt[10050]; int a,b,n; int p[5050],q[5050],r[5050],s[5050]; vector<int> vx,vy; vector<T> event; ll size(int x,int y) { if(x+1>=(int)vx.size()||y+1>=(int)vy.size())return 0ll; return (ll)(vx[x+1]-vx[x])*(ll)(vy[y+1]-vy[y]); } int main() { scanf("%d",&n); scanf("%d %d",&a,&b); for(int i=0;i<n;i++) { scanf("%d %d %d %d",&p[i],&q[i],&r[i],&s[i]); p[i]--;q[i]--; vx.pb(p[i]);vy.pb(q[i]);vx.pb(r[i]);vy.pb(s[i]); } sort(all(vx)); sort(all(vy)); vx.erase(unique(all(vx)),vx.end()); vy.erase(unique(all(vy)),vy.end()); for(int i=0;i<n;i++) { p[i]=lower_bound(all(vx),p[i])-vx.begin(); q[i]=lower_bound(all(vy),q[i])-vy.begin(); r[i]=lower_bound(all(vx),r[i])-vx.begin(); s[i]=lower_bound(all(vy),s[i])-vy.begin(); //printf("%d %d %d %d\n",p[i],q[i],r[i],s[i]); event.pb(T(P(p[i],q[i]),1)); event.pb(T(P(p[i],s[i]),-1)); event.pb(T(P(r[i],q[i]),-1)); event.pb(T(P(r[i],s[i]),1)); } sort(all(event)); int SX = vx.size(),SY = vy.size(); int id = 0; int ans_sz = 0; ll ans_num = 0ll; for(int i=0;i<=SX;i++) { if(!(id<event.size()))break; if(event[id].fi.fi!=i)continue; memset(cnt,0,sizeof(cnt)); while(id<event.size()&&event[id].fi.fi==i) { cnt[event[id].fi.sec]+=event[id].sec; id++; } for(int j=0;j<=SY;j++)cnt[j+1]+=cnt[j]; for(int j=0;j<=SY;j++) { imos[j]+=cnt[j]; if(ans_sz<imos[j]) { ans_sz = imos[j]; ans_num = size(i,j); } else if(ans_sz==imos[j]) { ans_num += size(i,j); } } } printf("%d\n",ans_sz); printf("%lld\n",ans_num); return 0; }