ac1225.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1225;
const
  maxchange=100001;
  treesize=524287;
  root=treesize shr 1+1;
var
  tree:array[1..treesize]of longint;
  n,limit,delta{real minus stored},total,leave,i,k:longint;
  c:char;
procedure ins(x:longint);
  var
    p,d:longint;
  begin
    p:=root;d:=p shr 1;
    while p<>x do begin
      inc(tree[p]);
      if p<x then inc(p,d) else dec(p,d);
      d:=d shr 1;
    end;
    inc(tree[p]);inc(total);
  end;
procedure erase(p,d:longint);
  begin
    if tree[p]=0 then exit;
    tree[p]:=0;
    if odd(p) then exit;
    erase(p-d,d shr 1);
    erase(p+d,d shr 1);
  end;
procedure del(x:longint);
  var
    p,d,c,t:longint;
  begin
    p:=root;d:=p shr 1;c:=0;
    while p<>x do begin
      if p<x then begin
        inc(c,tree[p]-tree[p+d]);
        inc(p,d);
      end
      else
        dec(p,d);
      d:=d shr 1;
    end;
    if not odd(p) then inc(c,tree[p-d]);
    inc(leave,c);dec(total,c);
    p:=root;d:=p shr 1;
    while p<>x do begin
      if p<x then begin
        t:=tree[p]-tree[p+d];
        dec(tree[p],c);dec(c,t);
        erase(p-d,d shr 1);
        inc(p,d);
      end
      else begin
        dec(tree[p],c);
        dec(p,d);
      end;
      d:=d shr 1;
    end;
    if not odd(p) then begin dec(tree[p],c);erase(p-d,d shr 1);end;
  end;
procedure find(k:longint);
  var
    p,d:longint;
  begin
    p:=root;d:=p shr 1;
    repeat
      if tree[p+d]>=k then
        inc(p,d)
      else if tree[p]-tree[p-d]>=k then
        break
      else begin
        dec(k,tree[p]-tree[p-d]);
        dec(p,d);
      end;
      d:=d shr 1;
    until odd(p);
    writeln(p+delta);
  end;
procedure traverse(p,d:longint);
  var
    t,i:longint;
  begin
    if tree[p]=0 then exit;
    if not odd(p) then traverse(p-d,d shr 1);
    if odd(p) then t:=tree[p] else t:=tree[p]-tree[p-d]-tree[p+d];
    for i:=1 to t do write(' ',p);
    if not odd(p) then traverse(p+d,d shr 1);
  end;
begin
  repeat
    fillchar(tree,sizeof(tree),0);
    readln(n,limit);delta:=-maxchange;total:=0;leave:=0;
    for i:=1 to n do begin
      readln(c,k);
      case c of
        'I':if k>=limit then ins(k-delta);
        'A':inc(delta,k);
        'S':begin dec(delta,k);del(limit-delta);end;
        'F':if k>total then writeln(-1) else find(k);
      end;
    end;
    writeln(leave);
  until seekeof;
end.