帮同学@Celtic 发的。

代码

#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define eps 1e-7
#define re register
#define N 1001001
#define MAX 2001
#define PI 3.1415927
using namespace std;
typedef long long ll;
typedef double db;
inline void read(re ll &ret)
{
    ret=0;re ll pd=0;re char c=getchar();
    while(!isdigit(c)){pd|=c=='-';c=getchar();}
    while(isdigit(c)){ret=(ret<<1)+(ret<<3)+(c^48);c=getchar();}
    ret=pd?-ret:ret;
    return;
}
ll n,ans,d;
struct node
{
	ll x,y;
}a[N];
deque<ll>q,p,p1,q1;
bool cmp(re node x,re node y)
{
	return x.x<y.x;
}
inline bool check(re ll x)
{
	while(!q.empty())
		q.pop_back();
	while(!p.empty())
		p.pop_back();
	while(!p1.empty())
		p1.pop_back();
	while(!q1.empty())
		q1.pop_back();
	for(re int i=1;i<=n;i++)
	{
		while(!q.empty()&&q.back()>=a[i].y)
			q.pop_back(),q1.pop_back();
		q.push_back(a[i].y);
		q1.push_back(a[i].x);
		while(!p.empty()&&p.back()<=a[i].y)
			p.pop_back(),p1.pop_back();
		p.push_back(a[i].y);
		p1.push_back(a[i].x);
		if(p.front()-q.front()>=d)
			return true;
		while(!q1.empty()&&q1.front()<a[i+1].x-x)
			q1.pop_front(),q.pop_front();
		while(!p1.empty()&&p1.front()<a[i+1].x-x)
			p1.pop_front(),p.pop_front();
	}
	return false;
}
int main()
{
	read(n);
	read(d);
	for(re int i=1;i<=n;i++)
	{
		read(a[i].x);
		read(a[i].y);
	}
	re ll l=1,r=n,mid;
	sort(a+1,a+n+1,cmp);
	while(l<=r)
	{
		mid=l+r>>1;
		if(check(mid))
			r=mid-1,ans=mid;
		else
			l=mid+1;
	}
	printf("%lld\n",ans);
    exit(0);
}