记录编号	95366	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2001] 金矿	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.170 s
提交时间	2014-04-05 21:06:30	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=15000+1000,INF=0x7fffffff;
int max(int a,int b,int c){return max(a,max(b,c));}
class SPLAYTREE{
public:
	class NODE{
	public:
		int key,data;//坐标和这个点的值
		int size;//子树大小
		int sum,mx;//子树和,最大前缀和
		NODE *lc,*rc,*f;
		NODE(int y,int t){size=1;key=y,data=sum=mx=t;}
		NODE(){NODE(0,0);}
	}*Nil,*left,*right,*Root;
	NODE* newNODE(int y,int t){
		NODE *T=new NODE(y,t);
		T->lc=T->rc=T->f=Nil;
		return T;
	}
	SPLAYTREE(){
		Nil=new NODE(INF/2,0);
		Nil->lc=Nil->rc=Nil->f=Nil;
		Nil->sum=Nil->mx=Nil->size=0;
		left=new NODE(-INF,0),right=new NODE(INF,0);
		left->lc=left->rc=left->f=Nil;
		right->lc=right->rc=right->f=Nil;
		left->sum=left->mx=right->sum=right->mx=0;
		left->rc=right,right->f=left;
		(left->size)++,Root=left;//边界节点
	}
	void update(NODE *T){
		T->size=T->lc->size+T->rc->size+1;
		T->sum=T->lc->sum+T->rc->sum+T->data;
		T->mx=max(T->lc->mx,T->lc->sum+T->data,T->lc->sum+T->data+T->rc->mx);
	}
	void zig(NODE *T){//右旋
		NODE *P=T->f,*rson=T->rc;
		if(Root==P) Root=T;
		else (P->f->lc==P)?P->f->lc=T:P->f->rc=T;
		T->f=P->f;P->f=T;
		T->rc=rson->f=P;P->lc=rson;
		update(P);
	}
	void zag(NODE *T){//左旋
		NODE *P=T->f,*lson=T->lc;
		if(P==Root) Root=T;
		else P->f->lc==P?P->f->lc=T:P->f->rc=T;
		T->f=P->f;P->f=T;
		T->lc=lson->f=P;P->rc=lson;
		update(P);
	}
	void splay(NODE *ANC,NODE *t){//t转到ANC
		if(t==ANC){
			update(t);
			return;
		}
		bool reach=false;
		while(!reach){
			NODE *P=t->f;
			if(P==ANC) (P->lc==t)?zig(t):zag(t),reach=true;
			else{
				if(P->f==ANC) reach=true;
				if(P->f->lc==P) (P->lc==t)?zig(P):zag(t),zig(t);
				else (P->lc==t)?zig(t):zag(P),zag(t);
			}
		}
		update(t);
	}
	void insert(NODE *T,int key,int data){//如果有则该点加data,否则新建一个点
		if(T->key==key){
			T->data+=data;
			splay(Root,T);
			return;
		}
		if(key<T->key){
			if(T->lc==Nil){
				T->lc=newNODE(key,data);
				T->lc->f=T;
				splay(Root,T->lc);
			}
			else insert(T->lc,key,data);
		}
		else{
			if(T->rc==Nil){
				T->rc=newNODE(key,data);
				T->rc->f=T;
				splay(Root,T->rc);
			}
			else insert(T->rc,key,data);
		}
	}
	void insert(int key,int data){
		insert(Root,key,data);
	}
}tree;
int ans=0;
int N;
pair<int,int> mine[SIZEN];
int S,W;
void work(void){
	int i=1,j,p=1;
	while(i<=N){
		j=i;
		while(j<=N&&mine[j].first==mine[i].first) j++;j--;
		//i~j为一段
		for(int k=i;k<=j;k++){
			tree.insert(mine[k].second,1);
			tree.insert(mine[k].second+W+1,-1);
		}
		while(mine[p].first<mine[i].first-S){
			tree.insert(mine[p].second,-1);
			tree.insert(mine[p].second+W+1,1);
			p++;
		}
		i=j+1;
		ans=max(ans,tree.Root->mx);
	}
	printf("%d\n",ans);
}
void read(void){
	scanf("%d%d%d",&S,&W,&N);
	for(int i=1;i<=N;i++) scanf("%d%d",&mine[i].first,&mine[i].second);
	sort(mine+1,mine+1+N);
}
int main(){
	freopen("kop.in","r",stdin);
	freopen("kop.out","w",stdout);
	read();
	work();
	return 0;
}