MDOLLS - Nested Dolls
Tác giả: ll931110
Ngôn ngữ: Pascal
Program MDOLLS;
Const
input = '';
output = '';
maxn = 20000;
Type
rec = record
h,w: integer;
end;
Var
a,s: array[1..maxn] of rec;
t,m,n,i: integer;
fi,fo: text;
Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);
Assign(fo, output);
Rewrite(fo);
End;
Procedure init;
Var
i: integer;
Begin
Readln(fi, m);
For i:= 1 to m do read(fi, a[i].w, a[i].h);
End;
Procedure swap(var x,y: rec);
Var
z: rec;
Begin
z:= x;
x:= y;
y:= z;
End;
Procedure quicksort;
Procedure partition(low,high: integer);
Var
i,j,p,q,k: integer;
Begin
If low >= high then exit;
i:= low;
j:= high;
k:= random(high - low + 1) + low;
p:= a[k].w;
q:= a[k].h;
Repeat
While (a[i].w > p) or ((a[i].w = p) and (a[i].h < q)) do inc(i);
While (a[j].w < p) or ((a[j].w = p) and (a[j].h > q)) do dec(j);
If i <= j then
Begin
If i < j then swap(a[i],a[j]);
inc(i);
dec(j);
End;
Until i > j;
partition(low,j);
partition(i,high);
End;
Begin
partition(1,m);
End;
Procedure update(i: integer);
Var
inf,sup,med,r: integer;
Begin
r:= 0;
inf:= 1;
sup:= n;
Repeat
med:= (inf + sup) div 2;
If (s[med].w > a[i].w) and (s[med].h > a[i].h) then
Begin
r:= med;
sup:= med - 1;
End
else inf:= med + 1;
Until inf > sup;
If r = 0 then
Begin
inc(n);
r:= n;
End;
s[r].w:= a[i].w;
s[r].h:= a[i].h;
End;
Procedure solve;
Var
i: integer;
Begin
n:= 1;
with s[1] do
Begin
h:= a[1].h;
w:= a[1].w;
End;
For i:= 2 to m do update(i);
Writeln(fo, n);
End;
Procedure closefile;
Begin
Close(fo);
Close(fi);
End;
Begin
openfile;
Readln(fi, t);
For i:= 1 to t do
Begin
init;
quicksort;
solve;
End;
closefile;
End.