记录编号	284086	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2001] 金矿	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.286 s
提交时间	2016-07-16 20:29:17	内存使用	4.87 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=150010;
const int maxl=99999999;
int n,s,w,i,j,ans,a[N],right[N];
struct point{
	int x,y;
	bool operator < (const point &X)const{return x<X.x;}
}p[N];

struct leaf{
	int l,r,add,Max;
}t[N];
void build(int x){
	if (t[x].l==t[x].r) return;
	int m=(t[x].l+t[x].r)/2;
	t[x*2].l=t[x].l;t[x*2].r=m;
	t[x*2+1].l=m+1;t[x*2+1].r=t[x].r;
	build(x*2);build(x*2+1);
}
void update(int x){
	if (t[x].l!=t[x].r){
		t[x*2].add+=t[x].add;
		t[x*2+1].add+=t[x].add;
		t[x*2].Max+=t[x].add;
		t[x*2+1].Max+=t[x].add;
	}
	t[x].add=0;
}
void change(int x,int l,int r,int add){
	if (t[x].l>r||t[x].r<l) return;
	update(x);
	if (t[x].l>=l&&t[x].r<=r){
		t[x].add+=add;
		t[x].Max+=add;
		for (int i=x/2;i>0;i/=2)
			t[i].Max=max(t[i*2].Max,t[i*2+1].Max);
		return;
	}
	change(x*2,l,r,add);change(x*2+1,l,r,add);
}
int getmax(){
	update(1);
	return t[1].Max;
}
int find(int x,int l,int r){
	if (l==r) return l;
	int m=(l+r)/2;
	return a[m]>=x?find(x,l,m):find(x,m+1,r);
}

int main()
{
	freopen("kop.in","r",stdin);
	freopen("kop.out","w",stdout);
	scanf("%d%d%d",&s,&w,&n);
	for (i=1;i<=n;i++){
		scanf("%d%d",&p[i].x,&p[i].y);
		a[i]=p[i].y;
	}
	sort(a+1,a+n+1);a[n+1]=maxl;
	t[1].l=1;t[1].r=n;build(1);
	for (i=j=1;i<=n;i++){
		while (a[j+1]<=a[i]+w) j++;
		right[i]=j;
	}
	sort(p+1,p+n+1);
	for (i=j=1;i<=n;i++){
		int l,r;
		while (j<=n&&p[j].x<=p[i].x+s){
			l=find(p[j].y,1,n);r=right[l];
			change(1,l,r,1);j++;
		}
		ans=max(ans,getmax());
		l=find(p[i].y,1,n);r=right[l];
		change(1,l,r,-1);
	}
	printf("%d\n",ans);
	return 0;
}