MSTICK - Wooden Sticks
Tác giả: khuc_tuan
Ngôn ngữ: Pascal
//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
{$mode delphi}
uses math;
type
Data = class
l, w : integer;
constructor init(l, w : integer);
end;
constructor Data.init(l, w : integer);
begin
self.l := l;
self.w := w;
end;
var
i, j, n, st, t : integer;
a : array[1..5000] of Data;
b : array[1..10000] of integer;
function get(i : integer) : integer;
var
r : integer;
begin
r := 0;
while i > 0 do
begin
inc(r, b[i]);
dec(i, i and (-i));
end;
get := r;
end;
procedure update(i, v : integer);
begin
while i <= 10000 do
begin
inc(b[i], v);
inc(i, i and (-i));
end;
end;
function findlast(i : integer) : integer;
var
le, ri, mi : integer;
begin
le := 1;
ri := i;
while le < ri do
begin
mi := (le + ri) div 2 + 1;
if get(i) - get(mi-1) > 0 then le := mi
else ri := mi - 1;
end;
findlast := le;
end;
function nhohon(a, b : Data) : boolean;
begin
nhohon := (a.l < b.l) or ((a.l = b.l) and (a.w < b.w));
end;
procedure sort(l, r : integer);
var
i, j : integer;
x, t : Data;
begin
if l>=r then exit;
i := l;
j := r;
x := a[(l+r) div 2];
repeat
while nhohon(a[i], x) do inc(i);
while nhohon(x, a[j]) do dec(j);
if i<=j then
begin
t := a[i]; a[i] := a[j]; a[j] := t;
inc(i); dec(j);
end;
until i > j;
sort(l,j);
sort(i,r);
end;
begin
read(st);
for t:=1 to st do
begin
read(n);
for i:=1 to n do
begin
a[i] := Data.Create;
read(a[i].l, a[i].w);
end;
sort( 1, n);
fillchar( b, sizeof(b), 0);
for i:=1 to n do
begin
if get(a[i].w) > 0 then
begin
j := findlast(a[i].w);
update( j, -1);
end;
update( a[i].w, 1);
end;
writeln(get(10000));
end;
end.