记录编号	574964	评测结果	AAWWEEEEEE
题目名称	双倍腹肌量	最终得分	20
用户昵称	lavey	是否通过	未通过
代码语言	C++	运行时间	1.166 s
提交时间	2022-08-30 20:45:47	内存使用	4.47 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,INF=0x3f3f3f3f;
struct node
{
	int pos,k;
};
int n,m,mx[N],mn[N];
bool vis[N]; 
bool judge(int len)
{
	deque<node> q1,q2;//mx mn
	int cnt=0;
	for(int i=1;i<=n;++i)
	{
		if(cnt>=m) return 1;
		if(!vis[i]) continue; 
		while(!q1.empty()&&i-q1.front().pos>=len) q1.pop_front();
		while(!q2.empty()&&i-q2.front().pos>=len) q2.pop_front();
		while(!q1.empty()&&q1.back().k<=mx[i]) q1.pop_back();
		q1.push_back((node){i,mx[i]});
		while(!q2.empty()&&q2.back().k>=mn[i]) q2.pop_back();
		q2.push_back((node){i,mn[i]});
		if(!q1.empty()&&!q2.empty()) cnt=max(cnt,q1.front().k-q2.front().k);
	}
	return cnt>=m;
}
int main()
{
	freopen("double_muscle.in","r",stdin);
	freopen("double_muscle.out","w",stdout);
	memset(mn,0x3f,sizeof(mn));
	memset(mx,0xcf,sizeof(mx));
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=n;++i) scanf("%d%d",&x,&y),vis[x]=1,mx[x]=max(mx[x],y),mn[x]=min(mn[x],y);
	int l=0,r=n;
	while(l<r)
	{
		int mid=(l+r)>>1;
		if(judge(mid)) r=mid;
		else l=mid+1;
	}
	printf("%d",l-1);
	return 0;
}