Problem: Example

Input

5 3
1 5
3 4
5 3
7 2
9 1


Output

5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
using vi=vector<int>;
#define PB push_back
#define ALL(x) x.begin(),x.end()

using pi=pair<int,int>;
int read(){
	int i;
	scanf("%d",&i);
	return i;
}
struct Pos{
	int x,y,i;
	bool operator<(Pos const& rhs)const{
		return x!=rhs.x?(x<rhs.x):(y<rhs.y);
	}
	bool operator==(Pos const&rhs)const{
		return x==rhs.x&&y==rhs.y;
	}
};
ostream& operator<<(ostream& os,Pos p){
	os<<"("<<p.x<<","<<p.y<<")";
	return os;
}
template<class T>
ostream& operator<<(ostream& os,vector<T> v){
	os<<"[";
	REP(i,v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}
const int Nmax=51400;
vi tr[Nmax];
int ng[Nmax];
void trDfs(int v,int w){
	ng[v]=w;
	for(auto ch:tr[v])trDfs(ch,w);
}
const int Size=1141919;
vi g[Size],revG[Size];
bool gVis[Size],rgVis[Size];
void SetEdge(int a,int b){
	g[a].PB(b);
	revG[b].PB(a);
}
int bufSize;
struct SegTree{
	int s;
	vector<vi> buf;
	void Init(int n){
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2);
	}
	void AddEdge(int b,int e,int v,int l,int r,int i){
		if(e<=l||r<=b)return;
		if(b<=l&&r<=e){
			if(!buf[i].empty())
				SetEdge(v,buf[i].back());
			return;
		}
		AddEdge(b,e,v,l,(l+r)/2,i*2);
		AddEdge(b,e,v,(l+r)/2,r,i*2+1);
	}
	void AddEdge(int b,int e,int v){
		if(b<e)AddEdge(b,e,v,0,s,1);
	}
	void AddVertex(int i,int v){
		i+=s;
		while(i>=1){
			int z=bufSize++;
			if(!buf[i].empty())
				SetEdge(z,buf[i].back());
			buf[i].PB(z);
			SetEdge(z,v);
			i/=2;
		}
	}
};
void chmin(int&a,int b){
	a=a<b?a:b;
}
const int inf=1145141919;
int main(){
	int n=read(),c=read();
	vector<Pos> ps(n);
	REP(i,n){
		int x=read(),y=read();
		ps[i]=Pos{x,y};
	}
	sort(ALL(ps));
	REP(i,n)ps[i].i=i;
	
	vector<Pos> convex{ps[0]};
	for(auto p:ps)if(p.y<convex.back().y)
		convex.PB(p);
	vi convIdx(n,-1);
	REP(i,n)if(ps[i].y<=ps[0].y)
		convIdx[i]=lower_bound(ALL(convex),ps[i],[](Pos a,Pos b){
			return a.y>=b.y;
		})-convex.begin()-1;
	
	map<int,vector<Pos>> yP;
	for(auto p:ps)yP[p.y].PB(p);
	set<pi> xI;
	memset(ng,-1,sizeof(ng));
	for(auto kv:yP){
		int y=kv.first;
		if(y<=ps[0].y){
			vector<Pos>const&w=kv.second;
			for(auto p:w){
				auto itr=xI.lower_bound(pi(p.x,-1));
				while(itr!=xI.end())
					if(itr->first<=p.x+c){
						tr[p.i].PB(itr->second);
						itr=xI.erase(itr);
					}else break;
				xI.insert(pi(p.x,p.i));
			}
			Pos a=w.front();
			int i=convIdx[a.i];
			if(convex[i]==a){
				auto itr=xI.lower_bound(pi(a.x+c+1,-1));
				while(itr!=xI.end()){
					trDfs(itr->second,i);
					itr=xI.erase(itr);
				}
			}
		}
	}
	
	bufSize=n;
	SegTree seg;
	seg.Init(n);
	for(auto kv:yP){
		vector<Pos>const& w=kv.second;
		for(auto p:w)
			seg.AddEdge(0,lower_bound(ALL(ps),Pos{p.x+c+1,-1})-ps.begin(),p.i);
		for(auto p:w)
			seg.AddVertex(p.i,p.i);
	}
	vi xs{-inf},is{Size-1};
	REP(i,n){
		int j=lower_bound(ALL(xs),ps[i].x-c)-xs.begin();
		SetEdge(i,is[j-1]);
		xs.PB(ps[i].x);
		int z=bufSize++;
		SetEdge(z,is.back());
		is.PB(z);
		SetEdge(z,i);
	}
	
	map<int,int> ascend;
	REP(i,n)ascend[ps[i].y]=inf;
	function<void(int)> rgDfs;
	rgDfs=[&](int v){
		if(rgVis[v])return;
		rgVis[v]=true;
		if(v<n){
			;//<<v<<endl;
			chmin(ascend[ps[v].y],ng[v]);
		}
		for(auto to:revG[v])rgDfs(to);
	};
	function<void(int)> gDfs;
	gDfs=[&](int v){
		if(gVis[v])return;
		;//<<"g"<<v<<endl;
		gVis[v]=true;
		for(auto to:g[v])gDfs(to);
		;//<<"h"<<v<<endl;
	};
	function<void(int,int,int)> trDfs2;
	trDfs2=[&](int v,int goal,int gy){
		;//<<"t"<<v<<endl;
		if(convIdx[v]>=goal||ps[v].y<=gy)gDfs(v);
		for(auto ch:tr[v])trDfs2(ch,goal,gy);
		;//<<"u"<<v<<endl;
	};
	for(auto itr=xI.end();itr!=xI.begin();){
		itr--;
		rgDfs(itr->second);
		int gy=(lower_bound(ALL(convex),Pos{itr->first+c+1,-1})-1)->y;
		int goal=ascend[gy];
		;//<<itr->second<<" "<<goal<<endl;
		trDfs2(itr->second,goal,gy);
		;//<<1919<<endl;
	}
	
	int ans=0;
	REP(i,n)if(gVis[i])
		ans++;
	cout<<ans<<endl;
}