MDOLLS - Nested Dolls

Tác giả: ladpro98

Ngôn ngữ: Pascal

uses    math;
type    e=record
        l,r:longint;
        end;
const   fi='';
        maxN=22222;
var     a:array[1..maxN] of e;
        f:array[1..maxN] of longint;
        tt,t,n,d:longint;
        inp:text;

procedure openF;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,t);
end;

procedure input;
var     i:longint;
begin
        readln(inp,n);
        for i:=1 to n do
        read(inp,a[i].l,a[i].r);

end;

procedure swap(i,j:longint);
var     t:e;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     p:e;
        i,j:longint;
begin
        if l>=r then exit;
        p:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while (a[i].l<p.l) or ((a[i].l=p.l) and (a[i].r>p.r)) do inc(i);
                while (a[j].l>p.l) or ((a[j].l=p.l) and (a[j].r<p.r)) do dec(j);
                if i<=j then
                begin
                        if i<j then swap(i,j);
                        inc(i);dec(j);
                end;
        until i>j;
        sort(l,j);sort(i,r);
end;


function find(r:longint; key:e):longint;
var     l,m,k:longint;
begin
        l:=1;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if (a[f[m]].l<key.l) and (a[f[m]].r<key.r) then
                begin
                        k:=m;
                        r:=m-1;
                end
                else l:=m+1;
        end;
        exit(k);
end;

procedure dp;
var     i:longint;
begin
        f[1]:=1;
        d:=1;
        for i:=2 to n do
        begin
                if (a[i].r<=a[f[d]].r) or (a[i].l<=a[f[d]].l) then
                begin
                        inc(d);
                        f[d]:=i;
                end
                else
                f[find(d,a[i])]:=i;
        end;
end;

begin
        openF;
        for tt:=1 to t do
        begin
                input;
                sort(1,n);
                dp;
                writeln(d);
        end;
end.

Download