题解 【AT2342 [AGC011F] Train Service Planning】

command_block · 2021-04-28 14:41:04 · 题解

题意 ： 有一条铁路，被 n+1 个站台分为 n 段。站台标号为 0\sim n ，铁路标号为 1\sim n。

列车通过第 i 段所需时间为 t_i ，可能是双向的或单向的。

现在需要设计一张列车（循环）时刻表。

对于所有的列车，要么从站台 0 前往站台 n ，要么从站台 n 前往站台 0 。

在单向轨道内，不能有两辆相反方向的车互相穿过。列车只能在站点停车等待。

若有一辆开往 n 的车在时刻 s 到达站点 i ，在时刻 t 离开站点 i ，则下一辆车恰好在时刻 s+k 到达站点 i ，在时刻 t+k 离开站点 i 。其中 k 是给定常数。

需要使得时间表中 0\rightarrow n 与 n\rightarrow 0 的列车的所需时间和最短。回答这个最小值，或指出无解。

下行车的区间为 \big(-St(i)-Sq(i),-St(i-1)-Sq(i)\big)

实际上下行车的式子是全体减去前缀得到后缀，但是走一整次所需的时间是 k 的倍数，所以在模 k 意义下可以忽略。这样形式上会更统一。

若这是单向铁路，要求两个区间（在模 k 意义下）不交。

记 x_i=Sp(i)+Sq(i) ，上式可以统一为 ：

对 x_{0\sim n} 的唯一约束是 ： 单调不减。

• 于是问题可以转化为 ：

  你有一个变量 x ，初始值任意。

  每次会给出一个模 k 意义下的区间，要求给 x 加一定值，使得 x 落在这个区间内。

  最小化加上的值的和。

  （在本题中，还需加上 2St(n) 才是答案）

考虑 \rm DP。记 dp_k[i] 为第 k 次操作后使得 x=i 所需的最小代价。

显然我们需要关心的 i 一定为给出的某个端点。

边界 ： dp_0[i]=0。

每次操作时，设给出的模意义区间为 [l,r] ，让 [l,r] 以外的位置转移到 l 上，然后将它们置为 \inf ，其余不变。

维护 dp_k[i]-i 的区间 \min 即可。

复杂度 O(n\log n)。

#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 100500
using namespace std;
const ll INF=1ll<<60;
ll x[MaxN<<1];int tn;
struct Node{
  ll x;bool fl;
  inline void ladd(){x=INF;fl=1;}
}a[MaxN<<2];
inline void up(int u)
{a[u].x=min(a[u<<1].x,a[u<<1|1].x);}
void build(int l=1,int r=tn,int u=1)
{
  if (l==r){a[u].x=-x[l];return ;}
  int mid=(l+r)>>1;
  build(l,mid,u<<1);
  build(mid+1,r,u<<1|1);
  up(u);
}
inline void ladd(int u){
  if (a[u].fl){
    a[u<<1].ladd();
    a[u<<1|1].ladd();
    a[u].fl=0;
  }
}
int to,wfl,wfr;ll wfc,ret;
void qry(int l=1,int r=tn,int u=1)
{
  if (wfl<=l&&r<=wfr){
    ret=min(ret,a[u].x);
    return ;
  }int mid=(l+r)>>1;ladd(u);
  if (wfl<=mid)qry(l,mid,u<<1);
  if (mid<wfr)qry(mid+1,r,u<<1|1);
}
void clr(int l=1,int r=tn,int u=1)
{
  if (wfl<=l&&r<=wfr){a[u].ladd();return ;}
  int mid=(l+r)>>1;ladd(u);
  if (wfl<=mid)clr(l,mid,u<<1);
  if (mid<wfr)clr(mid+1,r,u<<1|1);
  up(u);
}
void chg(int l=1,int r=tn,int u=1)
{
  if (l==r){
    a[u].x=min(a[u].x,wfc-x[l]);
    return ;
  }int mid=(l+r)>>1;ladd(u);
  if (to<=mid)chg(l,mid,u<<1);
  else chg(mid+1,r,u<<1|1);
  up(u);
}
ll dfs(int l=1,int r=tn,int u=1)
{
  if (l==r)return a[u].x+x[l];
  int mid=(l+r)>>1;ladd(u);
  return min(dfs(mid+1,r,u<<1|1),dfs(l,mid,u<<1));
}
int n,m,k;
ll t[MaxN];
struct Data{ll l,r;}b[MaxN];
int main()
{
  scanf("%d%d",&n,&k);
  for (int i=1,op;i<=n;i++){
    scanf("%lld%d",&t[i],&op);
    if (op==1&&2*t[i]>k){puts("-1");return 0;}
    t[i]+=t[i-1];
    if (op==1)
      b[++m]=(Data){(k-2*t[i-1]%k)%k,(k-2*t[i]%k)%k};
  }
  for (int i=1;i<=m;i++){
    x[++tn]=b[i].l;
    x[++tn]=b[i].r;
  }x[++tn]=0;
  sort(x+1,x+tn+1);
  tn=unique(x+1,x+tn+1)-x-1;
  build();
  for (int i=1;i<=m;i++){
    int tl=lower_bound(x+1,x+tn+1,b[i].l)-x,
        tr=lower_bound(x+1,x+tn+1,b[i].r)-x;
    wfc=INF;
    if (tl<=tr){
      wfl=1;wfr=tl-1;
      if (wfl<=wfr){
        ret=INF;qry();clr();
        wfc=b[i].l+ret;
      }
      wfl=tr+1;wfr=tn;
      if (wfl<=wfr){
        ret=INF;qry();clr();
        wfc=min(wfc,b[i].l+k+ret);
      }
    }else {
      wfl=tr+1;wfr=tl-1;
      if (wfl<=wfr){
        ret=INF;qry();clr();
        wfc=b[i].l+ret;
      }
    }to=tl;chg();
  }printf("%lld",2*t[n]+dfs());
  return 0;
}