记录编号	167833	评测结果	AAAAAAAAAAAAAAA
题目名称	[USACO Open08]牛的邻居	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	1.613 s
提交时间	2015-06-29 10:23:06	内存使用	7.18 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#define CL(x) memset(x,0,sizeof(x))
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std;
typedef long long LL;
int read(){
    int ret=0,f=1;
    char x=getchar();
    while(!(x>='0' && x<='9')){if(x=='-')f=-1;x=getchar();}
    while(x>='0' && x<='9') ret=ret*10+x-'0', x=getchar();
    return ret*f;
}
 
const int MAXN=100000+10;
const int INF=1e9;
 
struct data{
    int x,y;
    int sum;
    int id;
    data(){ x=y=id=sum=0; }
    bool operator < (const data & d)const{
        if(!d.id) return false;
        if(sum!=d.sum) return sum<d.sum;
        if(x!=d.x) return x<d.x;
        return d.y<d.y;
    }
}ds[MAXN];
bool cmpx(const data & a,const data & b){
    if(a.x!=b.x) return a.x<b.x;
    else return a.y<b.y;
}
LL X[MAXN],Y[MAXN];
LL x_ren[MAXN],y_ren[MAXN];
int N,C;
 
struct union_find_set{
    int fa[MAXN];
    void init(){ rep(i,0,MAXN-1) fa[i]=i; }
    union_find_set(){ init(); }
    int get_fa(int n){
        if(n!=fa[n]) fa[n]=get_fa(fa[n]);
        return fa[n];
    }
    bool uni(int a,int b){
        int af=get_fa(a);
        int bf=get_fa(b);
        if(af==bf) return false;
        fa[af]=bf;
        return true;
    }
}ufs;
int dis(const data & a,const data & b){
    return abs(X[a.id]-X[b.id]) + abs(Y[a.id]-Y[b.id]);
}
struct tree_arr{
    data a[MAXN];
    void init(){
        rep(i,0,MAXN-1) a[i]=data();
    }
    int lowbit(int n){ return n&-n; }
    void set(int p,data d){
        while(p<MAXN){
            if(a[p].id && dis(a[p],d)<=C) ufs.uni(a[p].id,d.id);
            a[p]=max(a[p],d);
            p+=lowbit(p);
        }
    }
    data get(int p){
        data ret;
        while(p){
            if(a[p].id && ret.id && dis(a[p],ret)<=C) ufs.uni(a[p].id,ret.id);
            ret=max(a[p],ret);
            p-=lowbit(p);
        }
        return ret;
    }
}at;
 
 
void cal_edge(){
    at.init();
    sort(ds+1,ds+1+N,cmpx);
    rep(i,1,N) ds[i].sum=X[ds[i].id] +Y[ds[i].id];
    rep(i,1,N){
        data d=at.get(ds[i].y);
        if(dis(d,ds[i])<=C) ufs.uni(ds[i].id,d.id);
        at.set(ds[i].y,ds[i]);
    }
}
 
void reverse_y(){
    rep(i,1,N) Y[i]=INF-Y[i]+1;
    rep(i,1,N) ds[i].y=Y[ds[i].id], y_ren[i]=ds[i].y;
    sort(y_ren+1,y_ren+1+N);
    rep(i,1,N) ds[i].y=lower_bound(y_ren+1,y_ren+1+N,ds[i].y)-y_ren;
}
 
void init(){
    N=read(), C=read();
    rep(i,1,N) ds[i].x=X[i]=read(), ds[i].y=Y[i]=read(), ds[i].id=i;
 
    reverse_y();
    cal_edge();
     
    reverse_y();
    cal_edge();
}
 
int sz[MAXN];
void work(){
    int num=0,mx_sz=0;
    rep(i,1,N){
        int f=ufs.get_fa(i);
        if(!sz[f]) num++;
        sz[f]++;
        mx_sz=max(mx_sz,sz[f]);
    }
    printf("%d %d\n",num,mx_sz);
}
 
int main(){
	freopen("nabor.in", "r", stdin);
	freopen("nabor.out", "w", stdout);
    init();
    work();
    return 0;
}