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.

Download