FIRS - Hàng cây
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$ifdef rr}
{$r+,q+}
{$mode objfpc}
{$inline off}
{$else}
{$r-,q-}
{$mode objfpc}
{$inline on}
{$endif}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 100111;
snode = 262144;
var
f1,f2 : text;
n,dead : longint;
nn : array[1..snode] of longint;
a : array[1..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do read(f1,a[i]);
end;
procedure init(i,l,r:longint); inline;
var
mid,x,y:longint;
begin
if (l=r) then
begin
nn[i]:=l;
exit;
end;
mid:=(l+r)>>1;
init(i<<1,l,mid);
init(i<<1+1,mid+1,r);
x:=nn[i<<1]; y:=nn[i<<1+1];
if a[x]<=a[y] then nn[i]:=x else nn[i]:=y;
end;
procedure update(i,l,r,u:longint); inline;
var
mid,x,y:longint;
begin
if (l>r) then exit;
if (u<l) or (r<u) then exit;
if (u=l) and (r=u) then exit;
mid:=(l+r)>>1;
update(i<<1,l,mid,u);
update(i<<1+1,mid+1,r,u);
x:=nn[i<<1]; y:=nn[i<<1+1];
if a[x]<=a[y] then nn[i]:=x else nn[i]:=y;
end;
procedure solve;
var
time,u:longint;
begin
dead:=0; time:=0;
while dead<n do
begin
inc(time);
u:=nn[1];
if (u>1) and (a[u-1]<MAXN) then
begin
a[u-1]:=MAXN;
update(1,1,n,u-1);
inc(dead);
end;
if (a[u]<MAXN) then
begin
a[u]:=MAXN;
update(1,1,n,u);
inc(dead);
end;
if (u<n) and (a[u+1]<MAXN) then
begin
a[u+1]:=MAXN;
update(1,1,n,u+1);
inc(dead);
end;
end;
writeln(f2,time);
end;
begin
openF;
inp;
init(1,1,n);
solve;
closeF;
end.