MSTICK - Wooden Sticks

Tác giả: ladpro98

Ngôn ngữ: Pascal

program mstick;
uses    math;
type    e=record
        l,r:longint;
        end;
const   fi='';
        maxN=5555;
var     b:array[1..maxN] of e;
        a,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,b[i].l,b[i].r);

end;

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

procedure sort(l,r:longint);
var     p:e;
        i,j:longint;
begin
        if l>=r then exit;
        p:=b[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while (b[i].l<p.l) or ((b[i].l=p.l) and (b[i].r<p.r)) do inc(i);
                while (b[j].l>p.l) or ((b[j].l=p.l) and (b[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;

procedure init;
var     i:longint;
begin
        for i:=1 to n do
        a[i]:=b[i].r;
end;

function find(r,key:longint):longint;
var     l,m,k:longint;
begin
        l:=1;
        while l<=r do
        begin
                m:=(l+r) shr 1;
                if a[f[m]]<=key 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]>=a[f[1]] then f[1]:=i
                else
                if a[i]<a[f[d]] 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);
                init;
                dp;
                writeln(d);
        end;
end.

Download