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.

Download