2013-09-21 16:50
裸
//
By BLADEVIL
var
n :longint;
i :longint;
x, y :longint;
t, tot :longint;
key, s, left, right :
array
[
0
..
100010
]
of
longint;
ft :longint;
a, b :longint;
ans :longint;
procedure
right_rotate(
var
t:longint);
var
k :longint;
begin
k:
=
left[t];
left[t]:
=
right[k];
right[k]:
=
t;
s[k]:
=
s[t];
s[t]:
=s[left[t]]+s[right[t]]+
1
;
t:
=
k;
end
;
procedure
left_rotate(
var
t:longint);
var
k :longint;
begin
k:
=
right[t];
right[t]:
=
left[k];
left[k]:
=
t;
s[k]:
=
s[t];
s[t]:
=s[left[t]]+s[right[t]]+
1
;
t:
=
k;
end
;
procedure
maintain(
var
t:longint;flag:boolean);
begin
if
not
flag
then
if
s[left[left[t]]]>s[right[t]]
then
right_rotate(t)
else
if
s[right[left[t]]]>s[right[t]]
then
begin
left_rotate(left[t]);
right_rotate(t);
end
else
exit
else
if
s[right[right[t]]]>s[left[t]]
then
left_rotate(t)
else
if
s[left[right[t]]]>s[left[t]]
then
begin
right_rotate(right[t]);
left_rotate(t);
end
else
exit;
maintain(left[t],false);
maintain(right[t],true);
maintain(t,true);
maintain(t,false);
end
;
procedure
insert(
var
t:longint; v:longint);
begin
if
t=
0
then
begin
inc(tot);
t:
=
tot;
key[t]:
=
v;
s[t]:
=
1
;
left[t]:
=
0
;
right[t]:
=
0
;
end
else
begin
inc(s[t]);
if
v<key[t]
then
insert(left[t],v)
else
insert(right[t],v);
maintain(t,v
>=
key[t]);
end
;
end
;
function
delete(
var
t:longint; v:longint):longint;
begin
dec(s[t]);
if
(v=key[t])
or
(v<key[t])
and
(left[t]=
0
)
or
(v>key[t])
and
(right[t]=
0
)
then
begin
delete:
=
key[t];
if
(left[t]=
0
)
or
(right[t]=
0
)
then
t:
=left[t]+right[t]
else
key[t]:
=delete(left[t],key[t]+
1
);
end
else
if
v<key[t]
then
delete:=delete(left[t],v)
else
delete:=
delete(right[t],v);
end
;
function
pre(
var
t:longint; v:longint):longint;
begin
if
t=
0
then
exit(-
1
);
if
v<key[t]
then
pre:=pre(left[t],v)
else
begin
pre:
=
pre(right[t],v);
if
pre=-
1
then
pre:=
key[t];
end
;
end
;
function
succ(
var
t:longint; v:longint):longint;
begin
if
t=
0
then
exit(-
1
);
if
key[t]<=v
then
succ:=succ(right[t],v)
else
begin
succ:
=
succ(left[t],v);
if
succ=-
1
then
succ:=
key[t];
end
;
end
;
begin
read(n);
ans:
=
0
;
t:
=
0
; tot:=
0
; s[t]:=
0
;
for
i:=
1
to
n
do
begin
read(x,y);
if
x=ft
then
insert(t,y)
else
if
s[t]=
0
then
begin
ft:
=
x;
insert(t,y);
end
else
begin
a:
=pre(t,y); b:=
succ(t,y);
if
a=-
1
then
a:=-maxlongint
div
10
;
if
b=-
1
then
b:=maxlongint
div
10
;
if
abs(b-y)<abs(y-a)
then
begin
ans:
=(ans+abs(b-y))
mod
1000000
;
b:
=
delete(t,b);
end
else
begin
ans:
=(ans+abs(y-a))
mod
1000000
;
a:
=
delete(t,a);
end
;
end
;
end
;
writeln(ans);
end
.
