CRATE - Coder Rating

Tác giả: ladpro98

Ngôn ngữ: Pascal

program crate;
uses    math;
type    e=record
        x,y,p:longint;
        end;
const   maxn=300055;
        maxV=100110;
        fi='';
var     a:array[0..maxn] of e;
        res:array[0..maxn] of longint;
        bit:array[0..maxV] of longint;
        n:longint;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                readln(inp,a[i].x,a[i].y);
                //inc(a[i].x);
                //inc(a[i].y);
                a[i].p:=i;
        end;
        close(inp);
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;
        t:e;
begin
        if l>=r then exit;
        t:=a[random(r-l+1)+l];
        i:=l;j:=r;
        repeat
                while (a[i].x<t.x) or ((a[i].x=t.x) and (a[i].y<t.y)) do inc(i);
                while (a[j].x>t.x) or ((a[j].x=t.x) and (a[j].y>t.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;

procedure update(i:longint);
begin
        while i<=maxV do
        begin
                inc(bit[i]);
                i:=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[i]);
                i:=i-i and (-i);
        end;
        exit(sum);
end;

procedure process;
var     i,j,k:longint;
begin
        i:=1;
        while i<=n do
        begin
                j:=i;
                while (j<=n) and (a[j].x=a[i].x) and (a[j].y=a[i].y) do inc(j);
                for k:=i to j-1 do
                res[a[k].p]:=get(a[k].y);
                for k:=i to j-1 do
                update(a[k].y);
                i:=j;
        end;
end;

procedure output;
var     i:longint;
begin
        for i:=1 to n do
        writeln(res[i]);
end;

begin
        input;
        sort(1,n);
        process;
        output;
end.

Download