MSE06H - Japan
Tác giả: ladpro98
Ngôn ngữ: Pascal
program mse06h;
uses math;
type e=record
x,y:longint;
end;
const fi='';
maxT=1101;
maxN=1101;
var bit:array[1..maxT,1..maxn] of longint;
a:array[1..maxn*maxn] of e;
m,n,k,t,tt,time,i,j,p:longint;
res:int64;
inp:text;
procedure update(i:longint);
begin
while i<=m do
begin
inc(bit[tt,i]);
inc(i,i and (-i));
end;
end;
function get(i:longint):longint;
var sum:longint;
begin
sum:=0;
while i>0 do
begin
inc(sum,bit[tt,i]);
dec(i,i and (-i));
end;
exit(sum);
end;
procedure swap(i,j:longint);
var t:e;
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
procedure sort(l,r:longint);
var i,j:longint;
p:e;
begin
if l>=r then exit;
i:=l;j:=r;
p:=a[random(r-l+1)+l];
repeat
while (a[i].x<p.x) or ((a[i].x=p.x) and (a[i].y<p.y)) do inc(i);
while (a[j].x>p.x) or ((a[j].x=p.x) and (a[j].y>p.y)) 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;
begin
assign(inp,fi);reset(inp);
readln(inp,t);
for tt:=1 to t do
begin
res:=0;
readln(inp,n,m,k);
for i:=1 to k do readln(inp,a[i].x,a[i].y);
sort(1,k);
i:=1;
while i<=k do
begin
j:=i;
while a[j].x=a[i].x do inc(j);
for p:=i to j-1 do
inc(res,get(m)-get(a[p].y));
for p:=i to j-1 do
update(a[p].y);
i:=j;
end;
writeln('Test case ',tt,': ',res);
end;
end.