传送门

这题难点是读题吧。。。(雾)

首先我们可以通过每层尽量往左移,使得$0\to N$的车不用在站点等待(即左上到右下的为一条直线),且至少有一个站点是会出现$0\to N$的车刚到,$N\to0$的车就马上从这个站点出发的情况(即两个方向的时间线会在某个站点处相交)。

我们可以进行DP,对于$i$号车站,处理出$N\to i$和$i\to0$最少的等待时间。为了转移这个DP,我们需要知道从一个站点开始,只要不会撞车就一直开,能一直开到哪个站点。如果我们把$B_i=2$的线段去掉,这其实就是从一个点引出射线,求跟已有线段的第一个交点的位置。这个直接用一个支持区间改值的线段树就行了。由于值域很大,需要动态开点,或者也可以离散化之后再做。DP完之后,我们直接枚举中间的交点,就能统计答案了。

#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#define MAXN 100010
#define LL long long
using namespace std;

namespace Seg{
    struct node{
        int lc,rc,max;
    }a[20000010];

    int size;

    int newnode(){
        int x=++size;
        a[x].lc=a[x].rc=a[x].max=0;
        return x;
    }

    void init(){
        size=0;
        newnode();
    }

    void setMax(int x,int cl,int cr,int l,int r,int v){
        if(l<=cl && cr<=r){
            a[x].max=v;
            return;
        }
        int mid=(cl+cr)>>1;
        if(l<=mid){
            if(!a[x].lc) a[x].lc=newnode();
            setMax(a[x].lc,cl,mid,l,r,v);
        }
        if(r>mid){
            if(!a[x].rc) a[x].rc=newnode();
            setMax(a[x].rc,mid+1,cr,l,r,v);
        }
    }

    int getMax(int x,int cl,int cr,int pos){
        if(cl==cr) return a[x].max;
        int mid=(cl+cr)>>1;
        if(pos<=mid && a[x].lc) return max(a[x].max,getMax(a[x].lc,cl,mid,pos));
        if(pos>mid && a[x].rc) return max(a[x].max,getMax(a[x].rc,mid+1,cr,pos));
        return a[x].max;
    }
}

int n;
LL a[MAXN],b[MAXN],k,s[MAXN];
LL f1[MAXN],f2[MAXN];

int main(){
#ifdef DEBUG
    freopen("F.in","r",stdin);
#endif
    scanf("%d%lld",&n,&k);
    bool flag=1;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",a+i,b+i);
        if(b[i]==1) flag=0;
        s[i]=s[i-1]+a[i];
    }
    if(flag){
        printf("%lld\n",s[n]*2);
        return 0;
    }
    LL now=0;
    Seg::init();
    for(int i=1;i<=n;i++){
        if(b[i]==1){
            int temp=min(k-1,now+2*a[i]-1);
            if(now+1<=temp) Seg::setMax(1,0,k-1,now+1,temp,i);
            if(now+2*a[i]-1>=k) Seg::setMax(1,0,k-1,0,now+2*a[i]-1-k,i);
        }
        now=(now+2*a[i])%k;
        int temp=Seg::getMax(1,0,k-1,now);
        if(!temp) f1[i]=s[i];
        else if(temp==i){
            puts("-1");
            return 0;
        }else{
            int pre=((now-(s[i]-s[temp])*2)%k+k)%k;
            f1[i]=f1[temp]+s[i]-s[temp]+(pre-now+k)%k;
        }
    }
    Seg::init();
    now=s[n]*2%k;
    for(int i=n;i>=1;i--){
        int temp=n-Seg::getMax(1,0,k-1,now)+1;
        if(temp==n+1) f2[i]=s[n]-s[i];
        else if(temp==i+1){
            puts("-1");
            return 0;
        }else{
            int pre=(now+(s[temp-1]-s[i])*2)%k;
            f2[i]=f2[temp-1]+s[temp-1]-s[i]+(now-pre+k)%k;
        }
        now=((now-2*a[i])%k+k)%k;
        if(b[i]==1){
            int temp=min(k-1,now+2*a[i]-1);
            if(now+1<=temp) Seg::setMax(1,0,k-1,now+1,temp,n-i+1);
            if(now+2*a[i]-1>=k) Seg::setMax(1,0,k-1,0,now+2*a[i]-1-k,n-i+1);
        }
    }
    LL ans=1LL<<62;
    for(int i=1;i<=n;i++)
        if(b[i]==1){
            ans=min(ans,f1[i]+f2[i]+s[n]);
        }
    printf("%lld\n",ans);
    return 0;
}