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.