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.

Download