记录编号	460383	评测结果	AAAAAAAAAA
题目名称	obc	最终得分	100
用户昵称	Bennettz	是否通过	通过
代码语言	C++	运行时间	0.082 s
提交时间	2017-10-16 21:37:32	内存使用	2.85 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 100005
struct Node{
	int x,y;
	bool operator <(const Node&b)const{
		if(x!=b.x)return x<b.x;
		else return y<b.y;
	}
}a[maxn],b[maxn];
int l[maxn],r[maxn],max1,max2;
int n,k,l1;
inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}
inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    register bool f = true;
    while(!isgraph(tmp)) tmp = getc();
    if(tmp == '-') f = false, tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 0x30),
        tmp = getc();
    if(f) return res;
    return ~res + 1;
}
inline int sum(Node a[]){
	int ans=0,s=0,ma=0;
	sort(a,a+n);
	l[0]=1;
	for(int i=1;i<n;i++){
		if(a[i].x!=a[i-1].x){
			s=i;
			l[i]=i-s+1;
		}
		else{
			while(a[i].y-a[s].y>l1){
				s++;
			}
			l[i]=i-s+1;
		}
	}
	if(k==1){
		for(int i=0;i<n;i++){
			ans=max(ans,l[i]);
		}
		return ans;
	}
	max1=max2=0;
	ma=l[0];
	for(int i=1;i<n;i++){
		if(a[i].x==a[i-1].x){
			ma=max(ma,l[i]);
		}
		else{
			if(ma>max1){
				max2=max1;
				max1=ma;
			}
			else if(ma>max2)max2=ma;
			ma=l[i];
		}
	}
	ans=max1+max2;
	s=n-1,r[n-1]=1;
	for(int i=n-2;i>=0;i--){
		if(a[i].x!=a[i+1].x){
			s=i;
			r[i]=s-i+1;
		}
		else{
			while(a[s].y-a[i].y>l1){
				s--;
			}
			r[i]=s-i+1;
		}
	}
	ma=0;
	for(int i=0;i<n;i++){
		ma=max(ma,l[i]);
		ans=max(ans,ma+r[i+1]);
	}
	return ans;
}
int main(){
	freopen("obc.in","r",stdin);
	freopen("obc.out","w",stdout);
	scanf("%d%d%d",&n,&k,&l1);
	if(!k){
		printf("0");
		return 0;
	}
	for(int i=0;i<n;i++){
		b[i].y=a[i].x=read(),b[i].x=a[i].y=read();
	}
	int ans=max(sum(a),sum(b));
	printf("%d",ans);
	return 0;
}