记录编号	574976	评测结果	AAAAAAAAAA
题目名称	双倍腹肌量	最终得分	100
用户昵称	ZRQ	是否通过	通过
代码语言	C++	运行时间	0.182 s
提交时间	2022-08-30 21:37:28	内存使用	4.36 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<deque>
#include<cmath>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
struct node
{
	int pos,k;
};
struct point
{
	int x,y;
}p[N];
int n,m,ans=INF;
int mx[N],mn[N];
bool cmp1(point a,point b)
{
	return a.x<b.x;
}
int main()
{
	freopen("double_muscle.in","r",stdin);
	freopen("double_muscle.out","w",stdout);
	memset(mx,0xcf,sizeof(mx));
	memset(mn,0x3f,sizeof(mn));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x,&p[i].y);
	sort(p+1,p+1+n,cmp1);	
	deque<node> q1,q2;
	int ed=2;
	for(int i=1;i<=n;++i)
	{
		if(i>=ed) q1.push_back((node){i,p[i].y}),q2.push_back((node){i,p[i].y}),ed=i+1;
		while(ed<=n&&q1.front().k-q2.front().k<m)
		{
			while(!q1.empty()&&q1.back().k<=p[ed].y) q1.pop_back();
			q1.push_back((node){ed,p[ed].y});
			while(!q2.empty()&&q2.back().k>=p[ed].y) q2.pop_back();
			q2.push_back((node){ed,p[ed].y});
			++ed;
		}
		if(ed==n+1&&q1.front().k-q2.front().k<m) break;
		ans=min(ans,abs(p[q1.front().pos].x-p[q2.front().pos].x));
		if(!q1.empty()&&q1.front().pos<=i) q1.pop_front();
		if(!q2.empty()&&q2.front().pos<=i) q2.pop_front();
//		printf("%d %d\n",i,ed);
	}
	printf("%d",ans);
	return 0;
}