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.