GOLD - Đảo giấu vàng

Tác giả: RR

Ngôn ngữ: Pascal

//Wishing myself a happy lunar new year with a lot of accept solutions
{$R+,Q+}
PROGRAM GOLD;
CONST
  FINP='';
  FOUT='';
  maxn=15000;
TYPE
  point=record x,y:longint; d:shortint; end;
VAR
  kq,sl,n,s,w:longint;
  phu,max:array[1..maxn*3] of longint;
  a:array[1..maxn*2] of point;
  b:array[1..maxn] of longint;
procedure readInput;
var
  f:text;
  i,u,v:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,s,w);
  readln(f,n);
  for i:=1 to n do
    begin
      readln(f,u,v);
      with a[2*i-1] do begin x:=u; y:=v; d:=1; end;
      with a[2*i] do begin x:=u; y:=v+w; d:=-1;end;
    end;
end;
procedure initB;
  procedure sort(l,r:longint);
  var
    i,j:longint;
    mid,temp:longint;
  begin
    i:=l; j:=r; mid:=b[(l+r) div 2];
    repeat
      while b[i]<mid do inc(i);
      while b[j]>mid do dec(j);
      if i<=j then
        begin
          temp:=b[i]; b[i]:=b[j]; b[j]:=temp;
          inc(i); dec(j);
        end;
    until i>j;
    if i<r then sort(i,r);
    if l<j then sort(l,j);
  end;
var
  i,j:longint;
begin
  for i:=1 to n do
    b[i]:=a[2*i].x;
  sort(1,n);
  j:=1;
  for i:=2 to n do
    if b[i]>b[j] then
      begin
        inc(j);
        b[j]:=b[i];
      end;
    sl:=j;
end;
function nhohon(a,b:point):boolean;
begin
  if a.y<b.y then nhohon:=true
  else if (a.y=b.y) and (a.d>b.d) then nhohon:=true
  else nhohon:=false;
end;
procedure sort(l,r:longint);
var
  i,j:longint;
  temp,mid:point;
begin
  i:=l; j:=r; mid:=a[(l+r) div 2];
  repeat
    while nhohon(a[i],mid) do inc(i);
    while nhohon(mid,a[j]) do dec(j);
    if i<=j then
      begin
        temp:=a[i]; a[i]:=a[j]; a[j]:=temp;
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure writeOutput;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
function max2(a,b:longint):longint;
begin
  if a>b then max2:=a else max2:=b;
end;
procedure update(i,s,t,left,right,d:longint);
var
  mid:longint;
begin
  if (b[s]>right) or (b[t]<left) then exit;
  if (left<=b[s]) and (b[t]<=right) then
    begin
      phu[i]:=phu[i]+d;
      max[i]:=max[i]+d;
      exit;
    end;
  mid:=(s+t) div 2;
  update(i shl 1,s,mid,left,right,d);
  update(i shl 1+1,mid+1,t,left,right,d);
  max[i]:=max2(max[i shl 1],max[i shl 1+1])+phu[i];
end;
procedure process;
var
  i:longint;
begin
  kq:=0;
  for i:=1 to 2*n do
    begin
      update(1,1,sl,a[i].x,a[i].x+s,a[i].d);
      if max[1]>kq then kq:=max[1];
    end;
end;
BEGIN
  readInput;
  initB;
  sort(1,2*n);
  process;
  writeOutput;
END.

Download