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.