QBDIVSEQ - Chia dãy

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
const
  FINP='';
  FOUT='';
  MAXN=100001;
var
  a,b:array[1..MAXN] of longint;
  k,n:longint;
  f1,f2:text;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do read(f1,a[i]);
end;
procedure ans; inline;
begin
  writeln(f2,k);
end;
var
  mid,gt:longint;
function find(l,r:longint):longint; inline;
begin
  if (b[l]<=gt) and (b[l-1]>gt) then exit(l);
  if (b[r]<=gt) and (b[r-1]>gt) then exit(r);
  mid:=(l+r)>>1;
  if (b[mid]<=gt) and (b[mid-1]>gt) then exit(mid)
  else if b[mid]<=gt then exit(find(l,mid-1))
  else exit(find(mid+1,r));
end;
procedure solve;
var
  i,j:longint;
begin
  k:=1; b[1]:=a[1];
  for i:=2 to n do
    begin
      if a[i]<b[k] then
        begin
          inc(k);
          b[k]:=a[i];
        end
      else if a[i]>=b[1] then
          b[1]:=a[i]
      else
        begin
          gt:=a[i];
          j:=find(2,k);
          b[j]:=a[i];
        end;
    end;
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Download