cashier_skiplist.pas 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207
  1. program cashier_skiplist;
  2. uses Sysutils;
  3. const
  4. infile='cashier.in';
  5. outfile='cashier.out';
  6. logfile='cashier_sk.log';
  7. p=0.5;
  8. Maxlevel=50;
  9. inf=1000000000;
  10. type
  11. snode=^node;
  12. arr=array[1..Maxlevel] of snode;
  13. arr2=array[1..MaxLevel] of longint;
  14. node=record
  15. key,pnum:longint;
  16. level:byte;
  17. link:arr;
  18. sum:arr2;
  19. end;
  20. slisttype=record
  21. level:byte;
  22. header,tail:snode;
  23. end;
  24. var
  25. StartTime:double;
  26. totnum:array[1..Maxlevel] of longint;
  27. update:array[1..Maxlevel] of snode;
  28. emptylink:arr;
  29. emptysum:arr2;
  30. f,fo:Text;
  31. totp,left,bottom,test,n,k,min:longint;
  32. order:char;
  33. slist:slisttype;
  34. procedure initialize;
  35. var
  36. c1:integer;
  37. begin
  38. randomize;
  39. bottom:=0; left:=0; totp:=0;
  40. fillchar(emptylink,sizeof(emptylink),0);
  41. fillchar(emptysum,sizeof(emptysum),0);
  42. slist.level:=1;
  43. new(slist.header);
  44. slist.header^.key:=-inf;
  45. slist.header^.pnum:=0;
  46. slist.header^.level:=1;
  47. slist.header^.sum:=emptysum;
  48. new(slist.tail);
  49. slist.tail^.key:=inf;
  50. slist.tail^.pnum:=0;
  51. slist.tail^.level:=1;
  52. slist.tail^.sum:=emptysum;
  53. slist.header^.level:=1;
  54. slist.header^.link:=emptylink;
  55. for c1:=1 to Maxlevel do slist.header^.link[c1]:=slist.tail;
  56. end;
  57. function Random_Num : integer;
  58. var
  59. tot:integer;
  60. begin
  61. tot:=1;
  62. while random<p do inc(tot);
  63. Random_Num:=tot;
  64. end;
  65. function Find(SearchKey:longint) : snode;
  66. var
  67. x:snode;
  68. c1:integer;
  69. begin
  70. x:=slist.header;
  71. for c1:=slist.level downto 1 do begin
  72. totnum[c1]:=0;
  73. while x^.link[c1]^.key<SearchKey do begin
  74. totnum[c1]:=totnum[c1]+x^.sum[c1];
  75. x:=x^.link[c1];
  76. end;
  77. update[c1]:=x;
  78. end;
  79. Find:=x;
  80. end;
  81. procedure Ins;
  82. var
  83. x:snode;
  84. c1:integer;
  85. tot:longint;
  86. t:snode;
  87. begin
  88. k:=k+bottom;
  89. if k<min+bottom then exit;
  90. x:=Find(k);
  91. if x^.link[1]^.key=k then begin
  92. x:=x^.link[1];
  93. inc(x^.pnum);
  94. for c1:=slist.level downto 1 do
  95. inc(update[c1]^.sum[c1]);
  96. end else begin
  97. new(t);
  98. t^.key:=k;
  99. t^.pnum:=1;
  100. t^.level:=Random_Num;
  101. if t^.level>Slist.level+1 then t^.level:=Slist.level+1;
  102. if t^.level>=slist.level then begin
  103. for c1:=slist.level+1 to t^.level+1 do begin
  104. update[c1]:=slist.header;
  105. update[c1]^.sum[c1]:=totp;
  106. slist.header^.link[c1]:=slist.tail;
  107. totnum[c1]:=0;
  108. end;
  109. slist.level:=t^.level+1;
  110. slist.header^.level:=slist.level;
  111. slist.tail^.level:=slist.level;
  112. end;
  113. t^.link:=emptylink;
  114. tot:=0;
  115. for c1:=1 to slist.level do begin
  116. if c1<=t^.level then begin
  117. t^.sum[c1]:=update[c1]^.sum[c1]-tot;
  118. t^.link[c1]:=update[c1]^.link[c1];
  119. update[c1]^.link[c1]:=t;
  120. update[c1]^.sum[c1]:=tot+t^.pnum;
  121. tot:=tot+totnum[c1];
  122. end else
  123. inc(update[c1]^.sum[c1],t^.pnum);
  124. end;
  125. end;
  126. inc(totp);
  127. end;
  128. procedure Add;
  129. begin
  130. dec(bottom,k);
  131. end;
  132. procedure Substract;
  133. var
  134. c1:integer;
  135. tot:longint;
  136. begin
  137. inc(bottom,k);
  138. Find(bottom+min);
  139. tot:=0;
  140. for c1:=1 to slist.level do begin
  141. slist.header^.link[c1]:=update[c1]^.link[c1];
  142. slist.header^.sum[c1]:=update[c1]^.sum[c1];
  143. dec(slist.header^.sum[c1],tot);
  144. inc(tot,totnum[c1]);
  145. end;
  146. while (slist.level>1)and(slist.header^.link[slist.header^.level-1]=slist.tail) do begin
  147. slist.header^.sum[slist.level]:=0;
  148. dec(slist.level);
  149. dec(slist.header^.level);
  150. dec(slist.tail^.level);
  151. end;
  152. inc(left,tot);
  153. dec(totp,tot);
  154. end;
  155. procedure Findnum;
  156. var
  157. x:snode;
  158. c1:integer;
  159. begin
  160. k:=totp-k+1;
  161. if k<=0 then writeln(fo,-1) else begin
  162. x:=slist.header;
  163. for c1:=slist.level downto 1 do begin
  164. while (x<>slist.tail)and(x^.sum[c1]<k)and(k>0)do begin
  165. dec(k,x^.sum[c1]);
  166. x:=x^.link[c1];
  167. end;
  168. end;
  169. x:=x^.link[1];
  170. writeln(fo,x^.key-bottom);
  171. end;
  172. end;
  173. begin
  174. Starttime:=time;
  175. initialize;
  176. assign(f,infile); reset(f);
  177. assign(fo,outfile); rewrite(fo);
  178. readln(f,n,min);
  179. for test:=1 to n do begin
  180. readln(f,order,k);
  181. case order of
  182. 'I':Ins;
  183. 'A':Add;
  184. 'S':Substract;
  185. 'F':FindNum;
  186. end;
  187. end;
  188. writeln(fo,left);
  189. close(fo);
  190. close(f);
  191. assign(f,logfile);
  192. rewrite(f);
  193. write(f,'Total Time : ');
  194. write(f,(time-starttime)*24*60*60:0:3);
  195. writeln(f,' s');
  196. close(f);
  197. end.