MINROAD - VOI 2014 - Con đường Tùng Trúc
Tác giả: ladpro98
Ngôn ngữ: Pascal
program minroad;
uses math;
type e=record
x,t:longint;
end;
const fi = '';
fo = '';
maxN = 300050;
var a :array[1..maxN] of e;
truc,tung :array[0..maxN] of longint;
n,res,p,q :longint;
procedure input;
var f:text;
i:longint;
begin
assign(f,fi);
reset(f);
readln(f,n,p,q);
for i:=1 to n do
readln(f,a[i].x,a[i].t);
close(f);
end;
procedure swap(i,j:longint);
var t:e;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
procedure sort(l,r:longint);
var p,i,j:longint;
begin
if l>=r then exit;
p:=a[random(r-l+1)+l].x;
i:=l;j:=r;
repeat
while a[i].x<p do inc(i);
while a[j].x>p do dec(j);
if i<=j then
begin
if i<j then swap(i,j);
inc(i);
dec(j);
end;
until i>j;
sort(l,j);sort(i,r);
end;
procedure init;
var i:longint;
begin
for i:=1 to n do
if a[i].t=1 then
begin
tung[i]:=tung[i-1]+1;
truc[i]:=truc[i-1];
end
else
begin
tung[i]:=tung[i-1];
truc[i]:=truc[i-1]+1;
end;
end;
procedure process;
var i,j:longint;
begin
res:=high(longint);
j:=2;
for i:=1 to n do
begin
while (j<=n) and (((tung[j]-tung[i-1])<p) or ((truc[j]-truc[i-1])<q)) do
inc(j);
if j<=n then
res:=min(res,a[j].x-a[i].x);
end;
end;
procedure output;
var f:text;
begin
assign(f,fo);
rewrite(f);
if res=high(longint) then res:=-1;
write(f,res);
close(f);
end;
begin
input;
sort(1,n);
init;
process;
output;
end.