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 1037. Memory Management

Help me!! Tell me how to improve my program ..I got TLE at test#5!
Posted by Ginforward 14 Apr 2008 14:48
program ural1037;
type
 tt=record
     lch,rch,cover,till1,a,b:longint;
    end;

var
 tree:array[1..60002]of tt;
 ans,nt,nb,tot,i,j,k,now:longint;
 s:string;
 flag:boolean;

procedure maketree(l,r:longint);
var
 now:longint;
begin
 inc(tot);
 now:=tot;
 tree[now].a:=l; tree[now].b:=r;
 tree[now].till1:=-1;
 if l<r then begin
  tree[now].lch:=tot+1;
  maketree(l,(l+r)shr 1);
  tree[now].rch:=tot+1;
  maketree((l+r)shr 1 +1,r);
 end;
end;

procedure coverit(now:longint);

 function max(x,y:longint):longint;
  begin
   if x>y then exit(x)
   else exit(y);
  end;

begin
 if (tree[now].a=tree[now].b)and(tree[now].a<>0)and((tree[now].cover=0)
  or(tree[now].till1<nt)) then begin
    tree[now].cover:=1;
        tree[now].till1:=nt+599;
    ans:=tree[now].a;
       end;
 if tree[now].a<>tree[now].b then begin
 if ans=-1 then coverit(tree[now].lch);
 if ans=-1 then coverit(tree[now].rch);
 if tree[now].a<tree[now].b then begin
  tree[now].till1:=max(tree[tree[now].lch].till1,tree[tree[now].rch].till1);
 if (tree[tree[now].lch].cover=1)and(tree[tree[now].rch].cover=1) then
  tree[now].cover:=1;
 end;
 end;
end;

procedure checkit(now:longint);
var
 mid:longint;

 function max(x,y:longint):longint;
  begin
   if x>y then exit(x)
   else exit(y);
  end;

begin
 mid:=(tree[now].a+tree[now].b)shr 1;
 if tree[now].till1<nt then exit
 else if (tree[now].a=tree[now].b)and
        (tree[now].till1>=nt) then begin
         tree[now].till1:=nt+599;
         flag:=true;
         exit;
 end
 else begin
       if nb<=mid then checkit(tree[now].lch)
       else checkit(tree[now].rch);
       if tree[now].a<tree[now].b then
        tree[now].till1:=max(tree[tree[now].lch].till1,tree[tree[now].rch].till1);
      end;
end;

begin
 tot:=0;
 maketree(0,30000);
 while not eof do begin
  readln(s);
  if pos('+',s)<>0 then begin
   val(copy(s,1,pos(' ',s)-1),nt);
   ans:=-1;
   coverit(1);
   writeln(ans);
  end
  else if pos('.',s)<>0 then begin
   val(copy(s,1,pos(' ',s)-1),nt);
   delete(s,1,pos('.',s)+1);
   val(s,nb);
   flag:=false;
   checkit(1);
   if flag then writeln('+')
   else writeln('-');
  end;
 end;
end.