ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1251. Cemetery Manager

const inp='';
      out='';
      daysize1=1001;
      daysize2=101;
      maxn=151;
      c:array[1..8,1..2] of longint=((-1,0),(1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1));

type datatype=array[0..maxn*maxn] of longint;

var client,size,ans,n,m:longint;
    treeperson,persontree,f,heavityperson,personheavity,h:datatype;

procedure add(p,data:longint);

begin
  while p<=size do begin
    inc(f[p],data);
    p:=p or (p-1)+1;
  end;
end;

function calc(p:longint):longint;

var tmp:longint;

begin
  tmp:=0;
  while p>0 do begin
    inc(tmp,f[p]);
    p:=p and (p-1);
  end;
  calc:=tmp;
end;

procedure heavity(p,nn:longint);

var tmph,tmpp,j:longint;

begin
  tmph:=h[p];tmpp:=heavityperson[p];
  j:=p shl 1;
  while j<=nn do begin
    if (j<nn)and(h[j+1]<h[j]) then inc(j);
    if h[j]<tmph then begin
      h[p]:=h[j];
      heavityperson[p]:=heavityperson[j];
      personheavity[heavityperson[p]]:=p;
      p:=j;j:=p shl 1;
    end
    else j:=nn+1;
  end;
  h[p]:=tmph;heavityperson[p]:=tmpp;
  personheavity[heavityperson[p]]:=p;
end;

procedure updata(p:longint);

var tmpp,tmph,j:longint;

begin
  j:=p shr 1;tmph:=h[p];tmpp:=heavityperson[p];
  while j>0 do
    if h[j]>tmph then begin
      h[p]:=h[j];heavityperson[p]:=heavityperson[j];
      personheavity[heavityperson[p]]:=p;
      p:=j;j:=p shr 1;
    end
    else break;
  h[p]:=tmph;heavityperson[p]:=tmpp;
  personheavity[heavityperson[p]]:=p;
end;

procedure main;

var nowx,z,nowy,xcurrent,ycurrent,now,w,current,l,r,day,d,i:longint;
    x:char;

begin
  assign(input,inp);reset(input);
  readln(n,m);size:=n*m;
  w:=0;
  repeat
    read(day);
    while (w>0)and(h[1]<=day) do begin
      now:=heavityperson[1];
      h[1]:=h[w];
      heavityperson[1]:=heavityperson[w];
      personheavity[heavityperson[1]]:=1;
      dec(w);
      if w>0 then heavity(1,w);
      add(persontree[now],-1);
      persontree[now]:=0;
    end;
    read(x);
    while (x<>'d')and(x<>'v') do read(x);
    if (x='d') then begin
      inc(client);l:=1;r:=size;
      if w<size then begin
        while l<r do begin
          d:=(l+r) shr 1;
          if calc(d)<d then r:=d else l:=d+1;
        end;
        add(r,1);
        treeperson[r]:=client;
        inc(w);
        heavityperson[w]:=client;
        h[w]:=day+daysize1;
        personheavity[client]:=w;
        persontree[client]:=r;
        updata(w);
      end
      else inc(ans);
    end
    else if x='v' then begin
      read(current);
      if persontree[current]>0 then begin
        h[personheavity[current]]:=day+daysize1;
        heavity(personheavity[current],w);
        xcurrent:=(persontree[current]-1) div m+1;
        ycurrent:=persontree[current]+m-xcurrent*m;
        for i:=1 to 8 do begin
          nowx:=xcurrent+c[i,1];
          nowy:=ycurrent+c[i,2];
          if (nowx>=1)and(nowx<=n)and(nowy>=1)and(nowy<=m) then
            z:=(nowx-1)*m+nowy
          else z:=0;
          if treeperson[z]>0 then
            if h[personheavity[treeperson[z]]]<day+daysize2 then begin
              h[personheavity[treeperson[z]]]:=day+daysize2;
              heavity(personheavity[treeperson[z]],w);
            end;
        end;
      end;
    end;
  until seekeof(input);
  assign(output,out);rewrite(output);
  writeln(ans);
  close(output);
end;

Begin
  Main;
End.