记录编号	575005	评测结果	WWWWEEEEEE
题目名称	双倍腹肌量	最终得分	0
用户昵称	Lesater	是否通过	未通过
代码语言	C++	运行时间	1.443 s
提交时间	2022-08-31 20:41:13	内存使用	8.03 MiB

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct Node{
    ll low,hig,now;
};
ll m,n,ans=INT_MAX;
Node h[100001];
bool cmp(Node a,Node b)
{
    return a.now<b.now;
}
int main()
{
    freopen("double_muscle.in","r",stdin);
    freopen("double_muscle.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=100001;++i)
    {
    h[i].low=INT_MAX;
    h[i].now=INT_MAX;
    }
    for(int i=1;i<=n;++i)
    {
        long long x,y;
        cin>>x>>y;
        h[x].now=x;
        h[x].low=min(h[x].low,y);
        h[x].hig=max(h[x].hig,y);
    }
    sort(h+1,h+100000,cmp);
    deque<Node> q;
    int l=1;
    ll hs=0,ls=INT_MAX;
    while(l<=n)
    {
        l++;
        int r=l;
        while(r<=n)
        {
        r++;
        q.push_front(h[r]);
        hs=max(hs,h[r].hig);
        ls=min(ls,h[r].low);
        while(hs-ls>=m)       
        {
            Node a=q.back();
            q.pop_back();
            if(q.back().low==l
            ||q.back().hig==hs)
            {
                q.push_back(a);
                break;
            }
            l++;
        }
        ans=min(ans,h[r].now-h[l].now);
        }
    }
    cout<<ans<<endl;
    return 0;
}