记录编号	574986	评测结果	AWAAAAAAAA
题目名称	双倍腹肌量	最终得分	90
用户昵称	yrtiop	是否通过	未通过
代码语言	C++	运行时间	0.299 s
提交时间	2022-08-31 12:49:18	内存使用	4.36 MiB

#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
const int INF = 1e9;

struct node {
    int x,y;
    node() {
        x = y = 0;
    }
}a[maxn];
int n,m;
int Qmax[maxn],head,tail;
int Qmin[maxn],Head,Tail;

int main() {
    freopen("double_muscle.in","r",stdin);
    freopen("double_muscle.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;++ i)scanf("%d %d",&a[i].x,&a[i].y);
    
    std::sort(a + 1 , a + 1 + n , [&](const node& p,const node& q) {
        return p.x < q.x;
    });
    int ans = INF;
    for(int i = 1,l = 1;i <= n;++ i) {
        for(;head <= tail&&a[Qmax[tail]].y <= a[i].y;-- tail)Qmax[tail] = 0;
        Qmax[++ tail] = i;
        for(;Head <= Tail&&a[Qmin[Tail]].y >= a[i].y;-- Tail)Qmin[Tail] = 0;
        Qmin[++ Tail] = i;
        
        while(a[Qmax[head]].y - a[Qmin[Head]].y >= m) {
            ans = std::min(ans , a[i].x - a[l].x);
            ++ l;
            for(;head <= tail&&Qmax[head] < l;++ head)Qmax[head] = 0;
            for(;Head <= Tail&&Qmin[Head] < l;++ Head)Qmin[Head] = 0;
        }
    }
    
    printf("%d",(ans ^ INF) ? ans : -1);
    return 0;
}