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.

Download