记录编号	433294	评测结果	AAAAAAAAAAAAAAA
题目名称	[POI 2001] 金矿	最终得分	100
用户昵称	하루Kiev	是否通过	通过
代码语言	C++	运行时间	0.198 s
提交时间	2017-08-05 09:49:26	内存使用	4.89 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxnn 150050
#define inf 0x7fffffff
using namespace std;
int s,w,n,a[maxnn],ls[maxnn],rs[maxnn],lazy[maxnn],maxx[maxnn];
struct node{
       int x,y;
       bool operator<(node A)const{
	        return x<A.x;
	   }
}e[maxnn];
int nxt[maxnn],ans;
void buildtree(int l,int r,int rt){
	 lazy[rt]=0;
	 ls[rt]=l;rs[rt]=r;
	 if(l==r) return;
	 int mid=(l+r)>>1;
	 buildtree(l,mid,rt*2);
	 buildtree(mid+1,r,rt*2+1);
	 maxx[rt]=max(maxx[rt*2],maxx[rt*2+1]);
}
void pushdown(int rt){
	 if(lazy[rt]){
	 	lazy[rt*2]+=lazy[rt];
	 	lazy[rt*2+1]+=lazy[rt];
	 	maxx[rt*2]+=lazy[rt];
	 	maxx[rt*2+1]+=lazy[rt];
	 	lazy[rt]=0;
	 }
}
void update(int l,int r,int L,int R,int rt,int c){
	 if(L<=l&&r<=R){
	 	lazy[rt]+=c;
	 	maxx[rt]+=c;
	 	return;
	 }
	 pushdown(rt);
	 int mid=(l+r)>>1;
	 if(L<=mid) update(l,mid,L,R,rt*2,c);
	 if(mid<R) update(mid+1,r,L,R,rt*2+1,c);
	 maxx[rt]=max(maxx[rt*2],maxx[rt*2+1]);
}
int find(int x,int l,int r){
	if(l==r) return l;
	int mid=(l+r)>>1;
	if(a[mid]>=x) return find(x,l,mid);
	else return find(x,mid+1,r);
}  
int main(){
    freopen("kop.in","r",stdin);
	freopen("kop.out","w",stdout);
	scanf("%d%d%d",&s,&w,&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&e[i].x,&e[i].y);
		a[i]=e[i].y;
	}
	sort(a+1,a+1+n);
	sort(e+1,e+1+n);
	a[n+1]=inf;
    int bj=1;
	for(int i=1;i<=n;i++){
    	while(a[bj+1]<=a[i]+w) bj++;
    	nxt[i]=bj;
	}bj=1;
	buildtree(1,n,1);
	for(int i=1;i<=n;i++){	
		while(bj<=n&&e[bj].x<=e[i].x+s){
			int l=find(e[bj].y,1,n);
			int r=nxt[l];
			update(1,n,l,r,1,1);
			bj++;
		}
		pushdown(1);
		ans=max(ans,maxx[1]);
		int l=find(e[i].y,1,n);
		int r=nxt[l];
		update(1,n,l,r,1,-1);
	}
	printf("%d\n",ans);
	return 0;
}