ac1111.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1111;
const
  maxn=500;
var
  s,e:array[1..maxn]of word;
  a,p:array[1..maxn*2]of word;
  n,i,j,x,y:word;
procedure qsort(s,t:word);
  var
    p,i,j,tmp:word;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tmp:=a[p];a[p]:=a[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (a[j]>=tmp) do dec(j);
      if i=j then break;a[i]:=a[j];inc(i);
      while (i<j) and (a[i]<=tmp) do inc(i);
      if i=j then break;a[j]:=a[i];dec(j);
    until i=j;
    a[i]:=tmp;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
function search(x:word):word;
  var
    l,r,m:word;
  begin
    l:=1;r:=j;
    repeat
      m:=(l+r) shr 1;
      if a[m]=x then break else if a[m]<x then l:=m+1 else r:=m-1;
    until false;
    search:=m;
  end;
begin
  repeat
    read(n);
    for i:=1 to n do begin
      read(s[i],e[i]);
      a[i*2-1]:=s[i];a[i*2]:=e[i];
    end;

    qsort(1,n*2);
    j:=1;
    for i:=2 to n*2 do
      if a[i]>a[j] then begin
        inc(j);a[j]:=a[i];
      end;

    fillchar(p,sizeof(p),0);
    for i:=1 to n do begin
      x:=search(s[i]);y:=search(e[i]);
      if x>p[y] then p[y]:=x;
    end;

    a[1]:=0;x:=0;
    for i:=2 to j do begin
      a[i]:=a[i-1];
      if (p[i]>0) and (a[p[i]]+1>a[i]) then a[i]:=a[p[i]]+1;
      if a[i]>x then x:=a[i];
    end;
    writeln(x);
  until seekeof;
end.