divide.pas

来自「Magio牛的usaco源代码」· PAS 代码 · 共 83 行

{
PROB:divide
LANG:PASCAL
}

program divide;
const
  maxn=1000;
  maxl=500000;
  maxr=1000;
var
  s,e:array[1..maxn]of longint;
  need:array[-maxr..maxl]of longint;
  n,l,a,b,i,j,min,count1,count2:longint;
  ok:boolean;
procedure qsort(u,v:word);
  var
    p,i,j:word;
    ts,te:longint;
  begin
    if u>=v then exit;
    p:=u+random(v-u+1);
    ts:=s[p];te:=e[p];s[p]:=s[u];e[p]:=e[u];
    i:=u;j:=v;
    repeat
      while (i<j) and (s[j]>=ts) do dec(j);
      if i=j then break;s[i]:=s[j];e[i]:=e[j];inc(i);
      while (i<j) and (s[i]<=ts) do inc(i);
      if i=j then break;s[j]:=s[i];e[j]:=e[i];dec(j);
    until i=j;
    s[i]:=ts;e[i]:=te;
    qsort(u,i-1);
    qsort(i+1,v);
  end;
begin
  assign(input,'divide.in');reset(input);
  assign(output,'divide.out');rewrite(output);

  read(n,l,a,b);l:=l shr 1;
  for i:=1 to n do begin
    read(s[i],e[i]);
    s[i]:=s[i] shr 1;
    e[i]:=(e[i]+1) shr 1;
  end;
  qsort(1,n);
  j:=1;
  for i:=2 to n do
    if s[i]<e[j] then begin
      if e[i]>e[j] then e[j]:=e[i];
      {In contest I just wrote e[j]:=e[i], and got WA}
    end
    else begin
      inc(j);
      s[j]:=s[i];e[j]:=e[i];
    end;
  n:=j;

  for i:=-maxr to -1 do need[i]:=-1;need[0]:=0;
  min:=-1;count1:=0;count2:=0;ok:=true;j:=1;
  for i:=1 to l do begin
    if need[i-a]>-1 then
      if min<0 then begin
        min:=need[i-a];count1:=1;
      end
      else
        if need[i-a]=min then inc(count1) else inc(count2);
    if need[i-b-1]=min then begin
      dec(count1);
      if count1=0 then
        if count2=0 then min:=-1 else begin inc(min);count1:=count2;count2:=0;end;
    end;
    if (j<=n) and (i=e[j]) then inc(j);
    if (j<=n) and (i>s[j]) or (min<0) then
      need[i]:=-1
    else
      if min<0 then begin ok:=false;break;end else need[i]:=min+1;
  end;

  if ok then writeln(need[l]) else writeln(-1);

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