$O(nlogn)$做法

#include<bits/stdc++.h>
using namespace std;
#define MAXN 114514
#define int long long

int n,d,maxx=0;

struct drop{
	int hei,x;
}a[MAXN];

bool cmp(drop x,drop y){
	return x.x<y.x;
}

bool check(int k){
	int h1=1,t1=1,h2=1,t2=1;
	drop q1[MAXN],q2[MAXN];
	for(int i=1;i<=n;i++){
		drop now=a[i];
		while(t1-h1>0 && q1[t1-1].hei<now.hei)t1--;
		while(t2-h2>0 && q2[t2-1].hei>now.hei)t2--;
		q1[t1++]=a[i],q2[t2++]=a[i];
		while(q1[h1].x<(now.x-k))h1++;
		while(q2[h2].x<(now.x-k))h2++;
		if((q1[h1].hei-q2[h2].hei)>=d)return true;
	}
	return false;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>n>>d;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].hei;
		maxx=max(maxx,a[i].x);
	}
	
	
	sort(a+1,a+n+1,cmp);
	
	int l=0,r=1000000,ans=-1;
	
	while(l<=r){		
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			r=mid-1;
			cout<<111<<endl;
		}else{
			l=mid+1;
		}
	}
	cout<<ans<<endl;
	
	
	return 0;
}