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.

Download