1
0

pet.pas 2.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120
  1. program pet;
  2. const
  3. infile='pet.in';
  4. outfile='pet.out';
  5. maxlevel=50;
  6. inf=2000000000;
  7. type
  8. snode=^node;
  9. arr=array[1..maxlevel] of snode;
  10. node=record
  11. lvl:integer;
  12. num:longint;
  13. link:arr;
  14. end;
  15. Listtype=record
  16. lvl:integer;
  17. head,tail:snode;
  18. end;
  19. var
  20. f,fo:text;
  21. ans,tot,state,currentstate,test,n,num:longint;
  22. empty:node;
  23. Slist:Listtype;
  24. update:array[1..maxlevel] of snode;
  25. procedure Initialize;
  26. begin
  27. ans:=0;
  28. fillchar(empty,sizeof(empty),0);
  29. Randomize;
  30. tot:=0;
  31. fillchar(slist,sizeof(slist),0);
  32. new(slist.head); new(slist.tail);
  33. slist.lvl:=1;
  34. slist.head^:=empty; slist.tail^:=empty;
  35. slist.head^.num:=-inf; slist.tail^.num:=inf;
  36. slist.head^.link[1]:=slist.tail;
  37. state:=0;
  38. end;
  39. function Random_Level : integer;
  40. var
  41. lvl:integer;
  42. begin
  43. lvl:=1;
  44. while random<0.5 do inc(lvl);
  45. Random_Level:=lvl;
  46. end;
  47. procedure find(o:longint);
  48. var
  49. c1:integer;
  50. x:snode;
  51. begin
  52. x:=slist.head;
  53. for c1:=slist.lvl downto 1 do begin
  54. while x^.link[c1]^.num<o do x:=x^.link[c1];
  55. update[c1]:=x;
  56. end;
  57. end;
  58. procedure ins(o:longint);
  59. var
  60. t:snode;
  61. c1:integer;
  62. begin
  63. inc(tot);
  64. find(o);
  65. new(t);
  66. t^:=empty;
  67. t^.num:=o;
  68. t^.lvl:=Random_Level;
  69. if t^.lvl>=slist.lvl then begin
  70. t^.lvl:=slist.lvl;
  71. inc(slist.lvl);
  72. slist.head^.link[slist.lvl]:=slist.tail;
  73. end;
  74. for c1:=1 to t^.lvl do begin
  75. t^.link[c1]:=update[c1]^.link[c1];
  76. update[c1]^.link[c1]:=t;
  77. end;
  78. end;
  79. procedure del(o:longint);
  80. var
  81. c1:integer;
  82. x:snode;
  83. begin
  84. dec(tot);
  85. find(o);
  86. if abs(update[1]^.num-o)<=abs(update[1]^.link[1]^.num-o) then begin
  87. x:=update[1];
  88. ans:=(ans+abs(update[1]^.num-o)) mod 1000000;
  89. end else begin
  90. x:=update[1]^.link[1];
  91. ans:=(ans+abs(update[1]^.link[1]^.num-o)) mod 1000000;
  92. end;
  93. find(x^.num);
  94. for c1:=1 to x^.lvl do
  95. update[c1]^.link[c1]:=x^.link[c1];
  96. while (slist.lvl>1)and(slist.head^.link[slist.lvl-1]=slist.tail) do dec(slist.lvl);
  97. end;
  98. begin
  99. Initialize;
  100. assign(f,infile); reset(f);
  101. assign(fo,outfile); rewrite(fo);
  102. readln(f,n);
  103. for test:=1 to n do begin
  104. readln(f,currentstate,num);
  105. if tot=0 then state:=currentstate;
  106. if currentstate=state then ins(num)
  107. else del(num);
  108. end;
  109. writeln(fo,ans);
  110. close(fo);
  111. close(f);
  112. end.