MSE06H - Japan
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$IFDEF RR}
{$R+,Q+}
{$Mode objFPC}
{$inline off}
{$ELSE}
{$R-,Q-}
{$Mode objFPC}
{$inline on}
{$ENDIF}
uses math;
const
FINP = {$IFDEF RR} 'input.txt'; {$ELSE} ''; {$ENDIF}
FOUT = {$IFDEF RR} 'output.txt'; {$ELSE} ''; {$ENDIF}
MAXN = 1000111;
type
BITree = object
val : array[1..MAXN] of longint;
procedure init;
procedure update(u:longint);
function get(u:longint):longint;
end;
var
f1,f2 : text;
n,m,k,test : longint;
a,b : array[1..MAXN] of longint;
bit : BITree;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n,m,k);
for i:=1 to k do
read(f1,a[i],b[i]);
end;
procedure swap(var a,b:longint); inline;
var
temp:longint;
begin
temp:=a; a:=b; b:=temp;
end;
procedure BITree.init; inline;
var
i:longint;
begin
for i:=m downto 1 do
val[i]:=0;
end;
procedure BITree.update(u:longint); inline;
var
v:longint;
begin
inc(val[u]);
v:=u+u and (-u);
if v<=m then update(v);
end;
function BITree.get(u:longint):longint; inline;
var
v,kq:longint;
begin
if u=0 then exit(0);
kq:=val[u];
v:=u-u and (-u);
if v>0 then inc(kq,get(v));
exit(kq);
end;
procedure sort(l,r:longint); inline;
var
i,j,ma,mb,key:longint;
begin
i:=l; j:=r; key:=l+random(r-l+1);
ma:=a[key]; mb:=b[key];
repeat
while (a[i]<ma) or ((a[i]=ma) and (b[i]<mb)) do inc(i);
while (a[j]>ma) or ((a[j]=ma) and (b[j]>mb)) do dec(j);
if i<=j then
begin
swap(a[i],a[j]);
swap(b[i],b[j]);
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l<j then sort(l,j);
end;
procedure solve;
var
i,u:longint;
count:int64;
begin
count:=0;
for i:=k downto 1 do
begin
u:=b[i];
inc(count,bit.get(u-1) );
bit.update(u);
end;
writeln(f2,'Test case ',test,': ',count);
end;
begin
openF;
read(f1,test);
for test:=1 to test do
begin
inp;
bit.init;
sort(1,k);
solve;
end;
closeF;
end.