Cod sursa(job #759913)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 19 iunie 2012 20:04:38
Problema Subsir crescator maximal Scor 100
Compilator fpc Status done
Runda Arhiva educationala Marime 1.13 kb
Program Subsir_crescator_maximal; {Complexitate n*log_n}
 var a,b,c:array [0..100001] of longint;
     i,n,poz,l,max:longint;
     fi,fo:text;
procedure cauta(x:longint);
 var st,dr,mid:longint;
begin
 st:=1; dr:=l; mid:=(st+dr) div 2;
  while st<=dr do begin
                   mid:=(st+dr) div 2;
                   if c[mid]>x then st:=mid+1
                           else dr:=mid-1;
                   end;
 poz:=dr;
end;
begin
 assign(fi,'scmax.in');
  assign(fo,'scmax.out');
 reset(fi); rewrite(fo); readln(fi,n);
  for i:=1 to n do read(fi,a[i]);
   b[n]:=1; c[0]:=1000000; c[1]:=a[n]; l:=1; max:=1;
  for i:=n-1 downto 1 do begin
                          cauta(a[i]);
                           b[i]:=poz+1;
                            if poz=l then inc(l);
                            if c[poz+1]<a[i] then c[poz+1]:=a[i];
                           if b[i]>max then max:=b[i];
                           end;
  writeln(fo,max); i:=1; poz:=0;
   while max>0 do
    if b[i]<>max then inc(i)
    else if (b[i]=max) and (a[i]>poz) then begin write(fo,a[i],' '); dec(max); poz:=a[i]; inc(i); end;
 close(fo);
end.