tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

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);
	}
}

もっと考える問題を解くべきなのかもしれない