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.