CRATE - Coder Rating

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=300010;
      maxc=100010;
var n:longint;
    a,b,d,re,e:array[1..maxn] of longint;
    f:array[0..maxc] of longint;

procedure sort(l,r:longint);
var x,y,i,j,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:=b[i]; b[i]:=b[j]; b[j]:=t;
                t:=a[i]; a[i]:=a[j]; a[j]:=t;
                t:=d[i]; d[i]:=d[j]; d[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;

procedure rf;
var i:longint;
begin
     assign(input,fi); reset(input);
     read(n);
     for i:=1 to n do
     begin
          read(a[i],b[i]);
          d[i]:=i;
     end;
     SORT(1,N);
     for i:=1 to n do e[d[i]]:=i;
     close(input);
end;

function sum(i:longint):longint;
var t:longint;
begin
     t:=0;
     while i>0 do
     begin
          t:=t+f[i];
          i:=i-i and (-i);
     end;
     sum:=t;
end;

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


procedure pr;
var i,j:longint;
begin
     for i:=1 to n do
     begin
          if (i>1) and (a[i]=a[i-1]) and (b[i]=b[i-1]) then re[i]:=re[i-1]
          else re[i]:=sum(b[i]);
          add(b[i]);
     end;
end;

procedure wf;
var i:longint;
begin
     assign(output,fo); rewrite(output);
     for i:=1 to n do writeln(re[e[i]]);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Download