Problem: Example

Input

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


Output

5

Solution (in CPP):

Solution:
bool debug=false;
#include <queue>
#include <vector>
#include <stdio.h>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
#define F first
#define S second
#define PB push_back
//#define int long long int
const int N=(int)1e5+10;
const int INF=(int)1e9+10;
struct seg_tree{
	vector<pair<int,int>> v;
	pair<int,int> better(const pair<int,int> &a,const pair<int,int> &b){return a.F<=b.F?a:b;}
	void pull(int n){v[n]=better(v[n*2+1],v[n*2+2]);}
	void init(int n,int l,int r,int a[]){
		if(l==r)v[n]=make_pair(a[l],l);
		else if(l<r){
			int mid=(l+r)>>1;
			init(n*2+1,l,mid,a);
			init(n*2+2,mid+1,r,a);
			pull(n);
		}
	}
	void fix(int n,int l,int r,int pos){
		if(l==r)v[n].F=INF;
		else if(l<r){
			int mid=(l+r)>>1;
			if(pos>mid)fix(n*2+2,mid+1,r,pos);
			else fix(n*2+1,l,mid,pos);
			pull(n);
		}
		return ;
	}
	pair<int,int> ask(int n,int l,int r,int L,int R){
	    //if(L>R)while(true);
		if(L<=l&&r<=R)return v[n];
		else if(L>r||l>R)return {INF,-1};
		else {
			int mid=(l+r)>>1;
			return better(ask(n*2+1,l,mid,L,R),ask(n*2+2,mid+1,r,L,R));
		}
	}
};
vector<pair<int,int>> v;
seg_tree sg;
int l[N],r[N],n,ans=0;
bool ok,went[N];
map<int,int> m;
void dfs(int x){
	ans++;
	went[x]=true;
	sg.fix(0,0,n-1,x);
	if(m.find(v[x].S)==m.end())m[v[x].S]=r[x];
	else m[v[x].S]=min(m[v[x].S],r[x]);
	if(debug)printf("fixed\n");
	pair<int,int> temp;
	if(debug)printf("going down\n");
	if(l[x]>0)while(true){
		temp=sg.ask(0,0,n-1,0,l[x]-1);
		if(temp.F<INF)dfs(temp.S);
		else break;
	}
	if(debug)printf("going mid\n");
	while(true){
		temp=sg.ask(0,0,n-1,l[x],r[x]);
		if(temp.F<v[x].S)dfs(temp.S);
		else break;
	}
	temp=sg.ask(0,0,n-1,l[x],r[x]);
	if(temp.F>v[x].S)ok=false;
	else if(temp.S>m[v[x].S])ok=false;
	if(debug)printf("return\n");
	return ;
}
int main(){
	int c,a[N],can=0,lpos=0,rpos=0,npos=0;
	pair<int,int> temp;
	ok=true;
	scanf("%d%d",&n,&c);
	for(int i=0;i<n;i++){
		scanf("%d%d",&temp.F,&temp.S);
		v.PB(temp);
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++)a[i]=v[i].S;
	sg.v.resize(N<<2);
	sg.init(0,0,n-1,a);
	//for(int i=0;i<n;i++)sg.ask(0,0,n-1,i,i);
	for(int i=0;i<n;i++)went[i]=false;
	v.PB({INF,INF});
	for(int i=0;i<n;i++){
	    lpos=lower_bound(v.begin(),v.end(),make_pair(v[i].F-c,0))-v.begin();
	    rpos=lower_bound(v.begin(),v.end(),make_pair(v[i].F+c+1,0))-v.begin();
		l[i]=lpos;
		r[i]=rpos-1;
	}
	if(debug)printf("before dfs\n");
	while(ok){
		while(npos<n){
			if(went[npos])npos++;
			else break;
		}
		if(npos<n)can=sg.ask(0,0,n-1,l[npos],r[npos]).S;
		else break;
		dfs(can);
	}
	printf("%d\n",ans);
}