因为是从下面给出的栅栏,为了方便起见,我们从下向上处理承接平台。

$f_{i,0}$表示走到$i$的左端点最小水平距离,$f_{i,1}$类似。

看看有哪些点可以走到$i$这个栅栏上,势必是$l_i<l_j<r_i~or~li<r_j<r_i$的栅栏才有可能到达$i$

因为牛是直线下落的,找到最上面(最晚出现)的能承接$l_{i}$的平台来接住牛,$r_i$也是一样的。

这个过程用线段树维护一下。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define gc getchar()
using namespace std;
const int N=3e4+10,G=2e5;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int tag[G<<2+5];
void update(int p,int l,int r,int ql,int qr,int tg)
{
    if(ql<=l&&qr>=r){tag[p]=tg;return ;}
    int mid=l+r>>1;
    if(ql<=mid)update(p<<1,l,mid,ql,qr,tg);
    if(qr>mid)update(p<<1|1,mid+1,r,ql,qr,tg);
}
int query(int p,int l,int r,int pos)
{
    if(l==r)return tag[p];
    int mid=l+r>>1,tg=0;
    if(pos<=mid)tg=max(query(p<<1,l,mid,pos),tg);
    else tg=max(query(p<<1|1,mid+1,r,pos),tg);
    return max(tg,tag[p]);
}
int l[N],r[N],prv[N][2],f[N][2];
int main()
{
    int n,s,mn=1e9,mx=-1e9;qr(n),qr(s);for(int i=1;i<=n;i++)qr(l[i]),qr(r[i]),mn=min(l[i],mn),mx=max(r[i],mx);
    mn=abs(mn)+1;mx+=mn;prv[1][0]=prv[1][1]=0;
    update(1,1,mx,l[1]+mn,r[1]+mn,1);
    for(int i=2;i<=n;i++)
    {
        prv[i][0]=query(1,1,mx,l[i]+mn);
        prv[i][1]=query(1,1,mx,r[i]+mn);
        update(1,1,mx,l[i]+mn,r[i]+mn,i);
    }
    memset(f,0x3f,sizeof(f));int ans=0x3f3f3f3f;
    f[n][0]=s-l[n],f[n][1]=r[n]-s;
    for(int i=n;i>=1;i--)
    {
        int j0=prv[i][0],j1=prv[i][1];
        if(!j0)ans=min(ans,f[i][0]+abs(l[i]));
        if(!j1)ans=min(ans,f[i][1]+abs(r[i]));
        f[j0][0]=min(f[j0][0],f[i][0]+l[i]-l[j0]);
        f[j0][1]=min(f[j0][1],f[i][0]+r[j0]-l[i]);
        f[j1][0]=min(f[j1][0],f[i][1]+r[i]-l[j1]);
        f[j1][1]=min(f[j1][1],f[i][1]+r[j1]-r[i]);
    }
    qw(min(ans,min(f[1][0]+abs(l[1]-0),f[1][1]+abs(r[1]-0))));puts("");
    return 0;
}