记录编号	151753	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2001] 金矿	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.235 s
提交时间	2015-03-10 17:13:53	内存使用	1.52 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 1e9
struct TREE{int f,l,r,z,e,Max,Sum;}A[30010];
struct point{
	int x,y,fi,se;
	bool operator<(const point& a)const{return x<a.x;}
}B[15010];

bool flag;
int s,w,n,i,p,zj1,zj,fa,ROOT,NOW,TEMP,sj=2,L=1,R=1,ans=0;
int limit[15010]={0},Stack[15010]={0},street[15010]={0};
void init()
{
	scanf("%d%d%d",&s,&w,&n);
	for(i=1;i<=n;i++)scanf("%d%d",&B[i].x,&B[i].y);
	sort(B+1,B+(n+1));
	for(i=2;i<=n;i++)if(B[i].x!=B[i-1].x)limit[++limit[0]]=i-1;
	limit[++limit[0]]=n;
}
inline void update(int &x)
{
    A[x].Sum=A[A[x].l].Sum+A[A[x].r].Sum+A[x].e;
    A[x].Max=max(A[A[x].l].Max,A[A[x].l].Sum+A[x].e);
    A[x].Max=max(A[x].Max,A[A[x].l].Sum+A[x].e+A[A[x].r].Max);
}
inline void ZIG(int &x)//右旋 
{
	fa=A[A[x].r].f=A[x].f,A[fa].l=A[x].r;
	if(A[x].f==A[A[fa].f].l)A[A[fa].f].l=x;
	else A[A[fa].f].r=x;
	zj=A[fa].f,A[fa].f=x,A[x].r=fa,A[x].f=zj;
	update(fa);
}
inline void ZAG(int &x)//左旋 
{
	fa=A[A[x].l].f=A[x].f,A[fa].r=A[x].l;
	if(A[x].f==A[A[fa].f].l)A[A[fa].f].l=x;
	else A[A[fa].f].r=x;
	zj=A[fa].f,A[fa].f=x,A[x].l=fa,A[x].f=zj;
	update(fa);
}
inline void splay(int u,int v)
{
	while(A[u].f!=v)
	{
		if(A[A[u].f].f==v)if(u==A[A[u].f].l)ZIG(u);else ZAG(u);
		else if(u==A[A[u].f].l)
		if(A[u].f==A[A[A[u].f].f].l)ZIG(A[u].f),ZIG(u);else ZIG(u),ZAG(u);
		else if(A[u].f==A[A[A[u].f].f].r)ZAG(A[u].f),ZAG(u);else ZAG(u),ZIG(u);
	}
	update(u);if(!v)ROOT=u;
}
inline void DELETE(int x)
{
	Stack[++Stack[0]]=x;splay(x,0);
	TEMP=A[x].l,NOW=A[x].r,A[NOW].f=0;
	while(A[NOW].l)NOW=A[NOW].l;splay(NOW,0);
	A[NOW].l=TEMP,A[TEMP].f=NOW;update(NOW);
}
inline int INSERT(int x,int E)
{
	NOW=ROOT;while(NOW)
	{
		street[++street[0]]=NOW;
		if(x<A[NOW].z||(x==A[NOW].z&&E<=A[NOW].e))
		NOW=A[NOW].l,flag=0;
		else NOW=A[NOW].r,flag=1;
	}
	if(Stack[0])NOW=Stack[Stack[0]--];else NOW=++sj;
	
    A[NOW].z=x,A[NOW].Sum=A[NOW].e=E,A[NOW].Max=max(E,0);
	zj1=A[NOW].f=street[street[0]],A[NOW].l=A[NOW].r=0;
	if(flag)A[zj1].r=NOW;else A[zj1].l=NOW;
	
	while(street[0])update(street[street[0]]),street[0]--;
	splay(NOW,0);return NOW;
}
void work()
{
	A[ROOT=1].r=2,A[1].z=-INF,A[2].f=1,A[2].z=INF;
	for(i=1;i<=limit[0];i++)
	{
		while(L<=R&&(B[limit[i]].x-B[L].x>s))
		DELETE(B[L].fi),DELETE(B[L].se),L++;
		
		while(B[R].x==B[limit[i]].x)
		B[R].fi=INSERT(B[R].y,1),B[R].se=INSERT(B[R].y+w+1,-1),R++;
		
		if(ans<A[ROOT].Max)ans=A[ROOT].Max;
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("kop.in","r",stdin);
	freopen("kop.out","w",stdout);
	init();
	work();
	return 0;
}