obstacle.pas

Magio牛的usaco源代码

{
PROB:obstacle
LANG:PASCAL
}

program obstacle;
const
  maxn=50000;
  treesize=131071;
  maxd=treesize shr 1+1;
var
  l,r,ld,rd:array[1..maxn]of longint;
  fence:array[-treesize..treesize]of word;
  solid:array[-treesize..treesize]of boolean;
  n,s,i,j:longint;
function min(a,b:longint):longint;
  begin
    if a<b then min:=a else min:=b;
  end;
function max(a,b:longint):longint;
  begin
    if a>b then max:=a else max:=b;
  end;
function findtree(x:longint):word;
  var
    p,d:longint;
  begin
    p:=0;d:=maxd;
    while (p<>x) and not solid[p] do begin
      if p<x then inc(p,d) else dec(p,d);
      d:=d shr 1;
    end;
    findtree:=fence[p];
  end;
procedure filltree(l,r,f,p,d:longint);
  begin
    if (d=0) or ((l=p-d*2+1) and (r=p+d*2-1)) then begin
      fence[p]:=f;solid[p]:=true;exit;
    end;
    if solid[p] then begin
      fence[p-d]:=fence[p];solid[p-d]:=true;
      fence[p+d]:=fence[p];solid[p+d]:=true;
    end;
    if (p>=l) and (p<=r) then fence[p]:=f;solid[p]:=false;
    if l<p then filltree(l,min(p-1,r),f,p-d,d shr 1);
    if r>p then filltree(max(p+1,l),r,f,p+d,d shr 1);
  end;
procedure cal(var x,d:longint);
  var
    f:word;
  begin
    f:=findtree(x);
    if f=0 then d:=abs(x) else d:=min(x-l[f]+ld[f],r[f]-x+rd[f]);
  end;
begin
  assign(input,'obstacle.in');reset(input);
  assign(output,'obstacle.out');rewrite(output);

  fence[0]:=0;solid[0]:=true;
  read(n,s);
  for i:=1 to n do begin
    read(l[i],r[i]);
    cal(l[i],ld[i]);cal(r[i],rd[i]);
    filltree(l[i],r[i],i,0,maxd);
  end;
  writeln(min(s-l[n]+ld[n],r[n]-s+rd[n]));

  close(input);close(output);
end.