PKU 2482 Stars in Your Window
http://poj.org/problem?id=2482
2次元平面上に星が散らばっている、w*hの枠の中に入っている星の明るさの合計を最大化したい。
最大値を求めろというような問題。
平面走査とか座標圧縮とか尺取。
わりとid:tozangezanさんの記事を参考にしました。
updateでy座標の[y,y+h)の範囲に星の明るさを足して、ある範囲での明るさの合計の最大値をmaxsumに保持しています。
いろいろと勘違いしていたせいで空間木みたいなものを作れば行けそうだと思い、間違った方向ですったもんだしてました。
ll sum[200000]; ll maxsum[200000]; void update(int l,int r,int al,int ar,int k,int x){ if(ar<=l || r<=al) return; if(l<=al && ar<=r){ sum[k] += x; maxsum[k] = max(maxsum[k*2+1],maxsum[k*2+2]) + sum[k]; return; } update(l,r,al,(al+ar)/2,k*2+1,x); update(l,r,(al+ar)/2,ar,k*2+2,x); maxsum[k] = max(maxsum[k*2+1],maxsum[k*2+2]) + sum[k]; } ll n,w,h; void solve(){ vector<pair<pair<ll,ll>,ll> > in; vector<ll> yin; rep(i,n){ ll x,y,c; cin>>x>>y>>c; in.pb(mp(mp(x,y),c)); yin.pb(y); yin.pb(y+h); } sort(ALL(in)); sort(ALL(yin)); yin.erase(unique(ALL(yin)),yin.end()); memset(maxsum,0,sizeof(maxsum)); memset(sum,0,sizeof(sum)); int s=0,t=0; ll ans = 0; while(t<SZ(in)){ while(in[s].F.F+w<=in[t].F.F){ update(lower_bound(ALL(yin),in[s].F.S)-yin.begin(), lower_bound(ALL(yin),in[s].F.S+h)-yin.begin(),0,SZ(yin),0,-in[s].S); ++s; } while(t<SZ(in) && in[s].F.F+w>in[t].F.F){ update(lower_bound(ALL(yin),in[t].F.S)-yin.begin(), lower_bound(ALL(yin),in[t].F.S+h)-yin.begin(),0,SZ(yin),0,in[t].S); ++t; } ans = max(ans,maxsum[0]); } cout<<ans<<endl; } main(){ while(cin>>n>>w>>h) solve(); }