记录编号	576422	评测结果	AAAAAAAAAA
题目名称	双倍腹肌量	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.614 s
提交时间	2022-10-08 19:06:58	内存使用	4.36 MiB

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n, m, ans;
struct node {
	int x, y;
}a[N];
bool cmp(node u, node v) {
	return u.x < v.x;
}
int p1[N], p2[N];
int h1, l2, t1, r2;  // 1存最大值，2存最小值 
int main() {
	freopen("double_muscle.in","r",stdin);
	freopen("double_muscle.out","w",stdout);
	cin >> n >> m; 
	for(int i = 1; i <= n; i ++) {
		cin >> a[i].x >> a[i].y;   //结构体便于排序 
	}
	sort(a + 1, a + 1 + n, cmp);
	ans = 0x3f3f3f3f;
	h1 = l2 = 1;
	for(int i = 0, j = 0; i <= n; i ++) {   //最外层循环拉左端点 
		while(h1 <= t1 && p1[h1] < i) {
			h1 ++;   //如果队首比左端点小，那么右移
		}
		while(l2 <= r2 && p2[l2] < i) {
			l2 ++;   //因为排序过了，编号小x一定小 
		}
		while(a[p1[h1]].y - a[p2[l2]].y < m && j < n) {
			j ++;
			while(h1 <= t1 && a[p1[t1]].y < a[j].y) {
				t1 --;
			}
			p1[++ t1] = j;
			while(l2 <= r2 && a[p2[r2]].y > a[j].y) {
				r2--;
			}
			p2[++ r2] = j;//更新两个单调队列 
		}
		if(j != n) {
			ans = min(ans, a[j].x - a[i].x);//满足条件 
		}
	} 
	if(ans == 0x3f3f3f3f){ //无解 
		cout << -1 << endl;
		return 0;
	}
	else {
		cout << ans << endl;
	}
}