Eva

Description

约翰建造了N(1≤N≤50000)个栅栏来与牛同乐．第i个栅栏的z坐标为[Ai.，Bi]（-100000≤Ai<Bi≤10^5），y坐标为i．牛棚的外栏即x轴，原点是牛棚的门．奶牛们开始处于(S，N)，她们需要回到牛棚的门（下图中用“*’表示）．

 约翰的初衷是为了给奶牛们练习跳跃，但是奶牛们似乎更愿意四蹄着地，慢慢她沿着栅栏

走．当她们走到栅栏的尽头，就会朝着牛棚的个栏方向（即y轴负方向）行走，直到碰上另一条栅栏或是牛棚外栏．这时候她们便要选择继续向左走，还是向右走．奶牛们希望走的路程最短．由于可方向的路程一定，你只需求出z方向走的最短路程，使奶牛回到原点．

Input

    第1行：N，S(-100000≤S≤100000)．

    第2到N+1行：每行2个整数Ai，Bi，(-100000≤Ai≤Bi≤100000)．

Output 

    最小的x方向的步数

Sample Input

4 0
-2 1
-1 2
-3 0
-2 1

Sample Output

4

HINT

/**************************************************************

    Problem: 3387

    User: ictsing

    Language: C++

    Result: Accepted

    Time:508 ms

    Memory:38588 kb

****************************************************************/

 

//3387 [Usaco2004 Dec]Fence Obstacle Course栅栏行动

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<map>

#include<queue>

#include<vector>

using namespace std;

struct fence

{

    int l,r;

} f[200000+5];

struct node

{

    int x,y;

};

int tree[2000005<<2];

int dis[200000+5];

bool vis[200000+5];

const int mt = 100000+5;

int to[mt<<1],nxt[mt<<1],w[mt<<1],adj[mt];

const int maxnn=100500;

inline int read()

{

    int num=0,flag=1;

    char ch;

    do

    {

        ch=getchar();

        if(ch=='-') flag=-1;

    }

    while(ch<'0'||ch>'9');

    do

    {

        num=num*10+ch-'0';

        ch=getchar();

    }

    while(ch>='0'&&ch<='9');

    return num*flag;

}

bool operator < (node a,node b)

{

    return a.y>b.y;

}

int ecnt=0;

int n,star;

void update(int rt,int l,int r,int lft,int rgt,int qwq)

{

    if(lft<=l&&r<=rgt)

    {

        tree[rt]=qwq;

        return ;

    }

    int mid=(l+r)>>1;

    if(lft<=mid) update(rt<<1,l,mid,lft,rgt,qwq);

    if(mid<rgt) update(rt<<1|1,mid+1,r,lft,rgt,qwq);

}

int query(int rt,int l,int r,int pos)

{

    //cout<<"QUERY "<<rt<<' '<<l<<' '<<r<<' '<<pos<<endl; 

    if(l==r)

    {

    //  cout<<"THIS IS "<<tree[rt]<<endl;

        return tree[rt];

    }

         

    int mid=(l+r)>>1;

    if(tree[rt]) tree[rt<<1]=tree[rt<<1|1]=tree[rt],tree[rt]=0;

    if(pos<=mid) return query(rt<<1,l,mid,pos);

    return query(rt<<1|1,mid+1,r,pos);

}

void adde(int u,int v,int ww)

{

    ecnt++,to[ecnt]=v,nxt[ecnt]=adj[u],w[ecnt]=ww,adj[u]=ecnt;

    //cout<<u<<" "<<v<<" "<<ww<<" qwq "<<endl;

}

void deal(int qwq)

{

    int tmpx=query(1,-maxnn,maxnn,f[qwq].l);

    //cout<<"ADDEDGEL "<<(tmpx<<1)<<' '<<(qwq<<1)<<endl;

    //cout<<"ADDEDGEL "<<(tmpx<<1|1)<<' '<<(qwq<<1)<<endl;

    adde(tmpx<<1,qwq<<1,abs(f[tmpx].l-f[qwq].l));

    adde(tmpx<<1|1,qwq<<1,abs(f[tmpx].r-f[qwq].l));

    int tmpy=query(1,-maxnn,maxnn,f[qwq].r);

    //cout<<"ADDEDGER "<<(tmpx<<1)<<' '<<(qwq<<1|1)<<endl;

    //cout<<"ADDEDGER "<<(tmpx<<1|1)<<' '<<(qwq<<1|1)<<endl;

    adde(tmpy<<1,qwq<<1|1,abs(f[tmpy].l-f[qwq].r));

    adde(tmpy<<1|1,qwq<<1|1,abs(f[tmpy].r-f[qwq].r));

    update(1,-maxnn,maxnn,f[qwq].l,f[qwq].r,qwq);

}

void dk()

{

    memset(dis,127,sizeof(dis));

    priority_queue<node>q;

    while(!q.empty()) q.pop();

    dis[0]=0;

    q.push((node)

    {

        0,0

    });

    while(!q.empty())

    {

        node u=q.top();

        q.pop();

        if(vis[u.x]) continue;

        vis[u.x]=1;

        for(int i=adj[u.x]; i; i=nxt[i])

        {

            int v=to[i];

            if(!vis[v]&&dis[v]>dis[u.x]+w[i])

            {

                dis[v]=dis[u.x]+w[i];

                q.push((node)

                {

                    v,dis[v]

                });

            }

        }

    }

}

int main()

{

    n=read(),star=read();

    //cout<<n<<endl;

    adde(0,1,0);

    for(int i=1; i<=n; i++)

    {

        f[i].l=read(),f[i].r=read(),

             deal(i);

        //cout<<f[i].l<<" "<<f[i].r<<" fuck "<<endl;

    }

    n++;

    f[n].l=f[n].r=star;

    deal(n);

    adde(n<<1,n<<1|1,0);

    dk();

    printf("%d\n",dis[n<<1|1]);

    return 0;

}