CRATE - Coder Rating

Tác giả: RR

Ngôn ngữ: Pascal

{$IFDEF debug}
  {$R+,Q+}
  {$Mode objFPC}
{$ELSE}
  {$R-,Q-}
  {$inline on}
{$ENDIF}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       300111;
type
  BITree        =       object
        val     :       array[1..100111] of longint;
        procedure update(u,k:longint);
        function get(u:longint):longint;
  end;

var
  f1,f2         :       text;
  n,maxb        :       longint;
  a,b,ind,better:       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); maxb:=-1;
      for i:=1 to n do
        begin
          read(f1,a[i],b[i]);
          maxb:=max(maxb,b[i]);
          ind[i]:=i;
        end;
    end;
procedure swap(var a,b:longint); inline;
    var
      temp:longint;
    begin
      temp:=a; a:=b; b:=temp;
    end;
    var
      ma,mb,key:longint;
procedure sort(l,r:longint); inline;
    var
      i,j: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]);
            swap(ind[i],ind[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 BITree.update(u,k:longint); inline;
    var
      v:longint;
    begin
      inc(val[u],k);
      v:=u+u and (-u);
      if v<=maxb then update(v,k);
    end;
function BITree.get(u:longint):longint; inline;
    var
      v,kq:longint;
    begin
      kq:=val[u];
      v:=u-u and (-u);
      if v>0 then inc(kq,get(v));
      exit(kq);
    end;
procedure solve;
    var
      i,count,last:longint;
    begin
      count:=0; last:=0;
      for i:=1 to n do
        if (a[i]=a[i-1]) and (b[i]=b[i-1]) then
          begin
            better[ind[i]]:=better[ind[i-1]];
            inc(count);
          end
        else
          begin
            if count>0 then bit.update(last,count);
            count:=1; last:=b[i];
            better[ind[i]]:=bit.get(b[i]);
          end;
      for i:=1 to n do
        writeln(f2,better[i]);
    end;

begin
  openF;
  inp;
  sort(1,n);
  solve;
  closeF;
end.

Download