QBDIVSEQ - Chia dãy

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
var test,it,n,re:longint;
    b,f:array[1..100000] of longint;

procedure rf;
var i:longint;
begin
     read(n);
     for i:=1 to n do read(b[i]);
end;

function bs(x:longint):longint;
var l,r,m,i:longint;
begin
     l:=1; r:=re;
     while l<=r do
     begin
          m:=(l+r) shr 1;
          if f[m]<=x then r:=m-1
          else l:=m+1;
     end;
     for i:=m-1 to m+1 do
          if (i>0) and (i<=re) and (f[i]<=x) then exit(i);
end;

procedure pr;
var i,x:longint;
begin
     re:=1; f[1]:=b[1];
     for i:=2 to n do
         if b[i]<f[re] then
         begin
              re:=re+1; f[re]:=b[i];
         end
         else
         begin
              x:=bs(b[i]);
              f[x]:=b[i];
         end;
     writeln(re);
end;

begin
     assign(input,fi); reset(input);
     rf;
     pr;
     close(input);
end.

Download