ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1037. Управление памятью

Help me!! Tell me how to improve my program ..I got TLE at test#5!
Послано Ginforward 14 апр 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.