PBCSEQ - Các đoạn nguyên

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
program PBCSEQ;
const
  FINP='';
  FOUT='';
  MAXN=100000;
  oo=1000000;
var
  kq,n:longint;
  a,b:array[1..MAXN] of longint;
  d:array[1..oo] of longint;
function max(a,b:longint):longint;
begin
  if a>b then max:=a else max:=b;
end;
procedure inp;
var
  f:text;
  i:longint;
begin
  assign(f,FINP); reset(f);
  readln(f,n);
  for i:=1 to n do
    readln(f,a[i],b[i]);
  close(f);
end;
procedure swap(var a,b:longint);
var
  temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint);
var
  mida,midb,i,j:longint;
begin
  i:=l; j:=r; mida:=a[(l+r) div 2]; midb:=b[(l+r) div 2];
  repeat
    while (a[i]>mida) or ((a[i]=mida) and (b[i]<midb)) do inc(i);
    while (a[j]<mida) or ((a[j]=mida) and (b[j]>midb)) do dec(j);
    if i<=j then
      begin
        swap(a[i],a[j]);
        swap(b[i],b[j]);
        inc(i); dec(j);
      end;
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j);
end;
procedure ans;
var
  f:text;
begin
  assign(f,FOUT); rewrite(f);
  writeln(f,kq);
  close(f);
end;
function get(u:longint):longint;
var
  kq,v:longint;
begin
  kq:=d[u];
  v:=u-u and (u xor (u-1));
  if v>0 then kq:=max(kq,get(v));
  get:=kq;
end;
procedure update(u,k:longint);
var
  v:longint;
begin
  d[u]:=max(d[u],k);
  v:=u+u and (u xor (u-1));
  if v<=oo then update(v,k);
end;
procedure solve;
var
  i,u:longint;
begin
  kq:=0;
  for i:=1 to n do
    begin
      u:=get(b[i]);
      if u+1>kq then kq:=u+1;
      update(b[i],u+1);
    end;
end;
begin
  inp;
  sort(1,n);
  solve;
  ans;
end.

Download