MSE06H - Japan

Tác giả: flashmt

Ngôn ngữ: Pascal

const  maxn=1001;
var test,it,m,n,k:longint;
    f:array[1..maxn] of longint;
    a,b:array[1..maxn*maxn] of longint;
    re:int64;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; y:=b[(i+j) shr 1];
     repeat
           while (a[i]>x) or ((a[i]=x) and (b[i]>y)) do i:=i+1;
           while (a[j]<x) or ((a[j]=x) and (b[j]<y)) do j:=j-1;
           if i<=j then
           begin
                t:=a[i]; a[i]:=a[j]; a[j]:=t;
                t:=b[i]; b[i]:=b[j]; b[j]:=t;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

function calc(x:longint):int64;
var r:int64;
begin
     r:=0;
     while x>0 do
     begin
          r:=r+f[x];
          x:=x-x and (-x);
     end;
     calc:=r;
end;

procedure add(x:longint);
begin
     while x<=n do
     begin
          f[x]:=f[x]+1;
          x:=x+x and (-x);
     end;
end;

procedure pr;
var i,x,y:longint;
begin
     read(m,n,k);
     re:=0;
     for i:=1 to k do read(a[i],b[i]);
     sort(1,k);
     fillchar(f,sizeof(f),0);
     for i:=1 to k do
     begin
          re:=re+calc(b[i]-1);
          add(b[i]);
     end;
     writeln('Test case ',it,': ',re);
end;

begin
     read(test);
     for it:=1 to test do pr;
end.

Download