PKU 2482 Stars in Your Window
考えずとも解ける簡単な平面走査をしていました。この類はいくらでも過去問ある気がする。
解法:問題の図を見て直感的にコードを書く
#include<stdio.h> #include<algorithm> using namespace std; long long p[10000]; long long q[10000]; int r[10000]; int segtree[65536]; long long X[20000]; long long Y[20000]; pair<pair<int,int>,pair<int,int> > event[20000];//(x,add),(y1,y2) void add(int a,int b,int c,int d,int e,int f){ if(a>d||b<c)return; if(c<=a&&b<=d){ segtree[e]+=f; }else{ add(a,(a+b)/2,c,d,e*2,f); add((a+b)/2+1,b,c,d,e*2+1,f); } if(e!=1){ if(segtree[e]>0||segtree[e^1]>0){ int d=max(segtree[e],segtree[e^1]); segtree[e]-=d; segtree[e^1]-=d; segtree[e/2]+=d; } if(segtree[e]<0&&segtree[e^1]<0){ int d=max(segtree[e],segtree[e^1]); segtree[e]-=d; segtree[e^1]-=d; segtree[e/2]+=d; } } } int main(){ int a,b,c; while(~scanf("%d%d%d",&a,&b,&c)){ for(int i=0;i<65536;i++)segtree[i]=0; for(int i=0;i<a;i++){ scanf("%lld%lld%d",p+i,q+i,r+i); p[i]*=2; q[i]*=2; } for(int i=0;i<a;i++){ X[i*2]=p[i]-b; X[i*2+1]=p[i]+b; Y[i*2]=q[i]-c; Y[i*2+1]=q[i]-1+c; } std::sort(X,X+a*2); std::sort(Y,Y+a*2); for(int i=0;i<a;i++){ event[i*2]=make_pair(make_pair(lower_bound(X,X+a*2,p[i]-b)-X,r[i]),make_pair(lower_bound(Y,Y+a*2,q[i]-c)-Y,lower_bound(Y,Y+a*2,q[i]+c-1)-Y)); event[i*2+1]=make_pair(make_pair(lower_bound(X,X+a*2,p[i]+b)-X,-r[i]),make_pair(lower_bound(Y,Y+a*2,q[i]-c)-Y,lower_bound(Y,Y+a*2,q[i]+c-1)-Y)); } std::sort(event,event+a*2); int ret=0; for(int i=0;i<a*2;i++){ add(0,32767,event[i].second.first,event[i].second.second,1,event[i].first.second); // printf("%d %d %d %d\n",event[i].first.first,event[i].first.second,event[i].second.first,event[i].second.second); ret=max(ret,segtree[1]); } printf("%d\n",ret); } }
もっと考える問題を解くべきなのかもしれない