MDOLLS - Nested Dolls

Tác giả: RR

Ngôn ngữ: Pascal

{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=20111;
var
  f1,f2:text;
  c,a,b:array[1..MAXN] of longint;
  sl,n,test:longint;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure inp;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do
    read(f1,a[i],b[i]);
end;
procedure swap(var a,b:longint);
var temp:longint;
begin
  temp:=a; a:=b; b:=temp;
end;
procedure sort(l,r:longint); inline;
var
  i,j,ma,mb,key:longint;
begin
  key:=random(r-l+1)+l;
  i:=l; j:=r; mb:=b[key]; ma:=a[key];
  repeat
    while (b[i]<mb) or ((b[i]=mb) and (a[i]>ma)) do inc(i);
    while (b[j]>mb) or ((b[j]=mb) and (a[j]<ma)) 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;
function find(key:longint):longint;
var
  l,r,mid,kq:longint;
begin
  l:=1; r:=sl;
  repeat
    mid:=(l+r)>>1;
    if c[mid]<key then
      begin
        kq:=mid;
        r:=mid-1;
      end
    else l:=mid+1;
  until l>r;
  exit(kq);
end;
procedure solve;
var
  u,i:longint;
begin
  sl:=1; c[1]:=a[1];
  for i:=2 to n do
    if a[i]<=c[sl] then
      begin
        inc(sl);
        c[sl]:=a[i];
      end
    else
      begin
        u:=find(a[i]);
        c[u]:=a[i];
      end;
end;
begin
  openF;
  read(f1,test);
  for test:=1 to test do
    begin
      inp;
      sort(1,n);
      solve;
      writeln(f2,sl);
    end;
  closeF;
end.

Download