C11CAVE - Hang động
Tác giả: ladpro98
Ngôn ngữ: Pascal
program c11cave;
uses math;
const fi='';
up=0;down=1;
maxN=500005;
var a:array[up..down,0..maxN] of longint;
f1,f2:array[1..maxN] of longint;
n,h,res,c:longint;
procedure input;
var f:text;
i:longint;
begin
assign(f,fi);
reset(f);
readln(f,n,h);
for i:=1 to n do
begin
if odd(i) then readln(f,a[down,i div 2 +1])
else readln(f,a[up,i div 2]);
end;
close(f);
end;
procedure swap(k,i,j:longint);
var t:longint;
begin
t:=a[k,i];
a[k,i]:=a[k,j];
a[k,j]:=t;
end;
procedure sort(k,l,r:longint);
var p,i,j:longint;
begin
if l>=r then exit;
p:=a[k,random(r-l+1)+l];
i:=l;j:=r;
repeat
while a[k,i]<p do inc(i);
while a[k,j]>p do dec(j);
if i<=j then
begin
if i<j then swap(k,i,j);
inc(i);dec(j);
end;
until i>j;
sort(k,l,j);sort(k,i,r);
end;
procedure process;
var i,j:longint;
begin
j:=1;
for i:=1 to H do
begin
while (j<=N div 2) and (a[down,j]<i) do inc(j);
f1[i]:=n div 2-j+1;
end;
j:=1;
for i:=H downto 1 do
begin
while (j<=N div 2) and (a[up,j]<(H-i+1)) do inc(j);
f2[i]:=n div 2-j+1;
end;
res:=maxN;
for i:=1 to H do res:=min(res,f1[i]+f2[i]);
for i:=1 to H do if (f1[i]+f2[i]=res) then inc(c);
end;
begin
input;
sort(up,1,n div 2);
sort(down,1,n div 2);
process;
write(res,' ',c);
end.