学步园

/*
 * poj2374 AC
 * 线段树+DP 这道题还是很典型的，值得一做。
 * 
 * */
#include<cstdio>
#include<algorithm>
#define MAXN 200005 
using namespace std; 

long tree[MAXN<<2];
long a[50005],b[50005];
long f[50000][2];

long query(long k,long l,long r,long i)
{
    if(k<l || k>r) return 0;
    if(l<=k && k<=r && tree[i])
        return tree[i];
    if(l==k && r==k) return tree[i];
    long mid = (l+r)>>1;
    return query(k,l,mid,i<<1)+query(k,mid+1,r,i<<1|1);
}

void pushdown(long i)
{
    tree[i<<1] = tree[i<<1|1] = tree[i];
    tree[i] = 0;
    return;
}

void insert(long k,long a,long b,long l,long r,long i)
{
    if(a>r || b<l) return;
    if(a<=l && r<=b)
    {
        tree[i] = k;
        return;
    }
    long mid = (l+r)>>1;
    if(tree[i]) pushdown(i);
    insert(k,a,b,l,mid,i<<1);
    insert(k,a,b,mid+1,r,i<<1|1);
    return;
}

int main()
{
    long n,s,i,j;
//    FILE* fin;
//    fin = fopen("d.in","r");

//  fscanf(fin,"%ld%ld",&n,&s);
    scanf("%ld%ld",&n,&s);
    a[0] = b[0] = 0;
    for(i=n;i>=1;i--)
    {
        scanf("%ld%ld",&a[i],&b[i]);
  //      fscanf(fin,"%ld%ld",&a[i],&b[i]);

        j = query(a[i],-100000,100000,1);
        f[i][0] = min(abs(a[i]-a[j])+f[j][0],abs(a[i]-b[j])+f[j][1]);

        j = query(b[i],-100000,100000,1);
        f[i][1] = min(abs(b[i]-a[j])+f[j][0],abs(b[i]-b[j])+f[j][1]);

        insert(i,a[i],b[i],-100000,100000,1);
    }
    long ans;
    ans = min(f[1][0]+abs(a[1]-s),f[1][1]+abs(b[1]-s));
    printf("%ld\n",ans);
  //  fclose(fin);
    return 0;
}