CRATE - Coder Rating

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program CRATE;
Const
  input  = '';
  output = '';
  maxn = 300000;
  maxd = 100000;
Type
  rec = record
    x,y,z: integer;
  end;
Var
  a: array[1..maxn] of rec;
  res: array[1..maxn] of integer;
  p: array[1..maxd] of integer;
  n: integer;

Procedure init;
Var
  f: text;
  i: integer;
Begin
  Assign(f, input);
    Reset(f);

  Readln(f, n);
  For i:= 1 to n do
    Begin
      Readln(f, a[i].x, a[i].y);
      a[i].z:= i;
    End;

  Close(f);
End;

Procedure swap(var s,t: rec);
Var
  tmp: rec;
Begin
  tmp:= s;
  s:= t;
  t:= tmp;
End;

Function low(s,t: rec): boolean;
Begin
  low:= (s.x < t.x) or ((s.x = t.x) and (s.y < t.y));
End;

Procedure quicksort;

  Procedure partition(l,h: integer);
  Var
    i,j: integer;
    pivot: rec;
  Begin
    If l >= h then exit;
    i:= l;
    j:= h;
    pivot:= a[random(h - l + 1) + l];

    Repeat
      While low(a[i],pivot) do inc(i);
      While low(pivot,a[j]) do dec(j);

      If i <= j then
        Begin
          If i < j then swap(a[i],a[j]);
          inc(i);
          dec(j);
        End;
    Until i > j;

    partition(l,j);
    partition(i,h);
  End;

Begin
  partition(1,n);
End;

Procedure update(v: integer);
Begin
  While v <= maxd do
    Begin
      inc(p[v]);
      v:= v + (v and (-v));
    End;
End;

Function calc(v: integer): integer;
Var
  t: integer;
Begin
  t:= 0;
  While v > 0 do
    Begin
      t:= t + p[v];
      v:= v - (v and (-v));
    End;

  calc:= t;
End;

Procedure solve;
Var
  i: integer;
Begin
  Fillchar(p, sizeof(p), 0);
  res[a[1].z]:= 0;
  update(a[1].y);

  For i:= 2 to n do
    Begin
      If (a[i].x = a[i - 1].x) and (a[i].y = a[i - 1].y)
         then res[a[i].z]:= res[a[i - 1].z] else res[a[i].z]:= calc(a[i].y);
      update(a[i].y);
    End;
End;

Procedure printresult;
Var
  f: text;
  i: integer;
Begin
  Assign(f, output);
    Rewrite(f);
    For i:= 1 to n do writeln(f, res[i]);
  Close(f);
End;

Begin
  init;
  quicksort;
  solve;
  printresult;
End.

Download