MSE06H - Japan

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program MSE06H;
Const
  input  = '';
  output = '';
  maxk = 1000000;
  maxn = 1000;
Type
  rec = record
    x,y: integer;
  end;
Var
  fi,fo: text;
  n,m,k,nTest,iTest: integer;
  a: array[1..maxn * maxn] of rec;
  b: array[1..maxn] of integer;
  tmp: array[1..maxn * maxn] of integer;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure init;
Var
  i: integer;
Begin
  Readln(fi, n, m, k);
  For i:= 1 to k do readln(fi, a[i].x, a[i].y);
End;

Procedure swap(var t1,t2: rec);
Var
  t3: rec;
Begin
  t3:= t1;
  t1:= t2;
  t2:= t3;
End;

Function low(t1,t2: rec): boolean;
Begin
  low:= (t1.x < t2.x) or ((t1.x = t2.x) and (t1.y < t2.y));
End;

Procedure quicksort;

  Procedure partition(l,h: integer);
  Var
    i,j: integer;
    p: rec;
  Begin
    If l >= h then exit;
    i:= l;
    j:= h;
    p:= a[random(h - l + 1) + l];

    Repeat
      While low(a[i],p) do inc(i);
      While low(p,a[j]) 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(l,j);
    partition(i,h);
  End;

Begin
  partition(1,k);
End;

Procedure update(v: integer);
Begin
  While v >= 1 do
    Begin
      inc(b[v]);
      v:= v - (v and (-v));
    End;
End;

Function calc(v: integer): int64;
Var
  t: int64;
Begin
  t:= 0;
  While v <= maxn do
    Begin
      t:= t + b[v];
      v:= v + (v and (-v));
    End;
  calc:= t;
End;

Procedure solve;
Var
  res: int64;
  num,i,j: integer;
Begin
  Fillchar(b, sizeof(b), 0);
  res:= 0;
  num:= 1;
  tmp[1]:= a[1].y;

  For i:= 2 to k do
    Begin
      If a[i].x = a[i - 1].x then
        Begin
          inc(num);
          tmp[num]:= a[i].y;
        End
      else
        Begin
          For j:= 1 to num do update(tmp[j] - 1);
          num:= 1;
          tmp[1]:= a[i].y;
        End;

      res:= res + calc(a[i].y);
    End;

  Writeln(fo, 'Test case ', iTest, ': ', res);
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;

  Readln(fi, nTest);
  For iTest:= 1 to nTest do
    Begin
      init;
      quicksort;
      solve;
    End;

  closefile;
End.

Download