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

Обсуждение задачи 1019. Перекрашивание прямой

My program 1019
Послано marvel 10 июн 2007 12:09
program ural1019;
type
  linetype=record
             a,b:longint;
             color:char;
           end;
  drawpoint=^node;
  node=record
         a,b:longint;
         color:char;
         next:drawpoint;
       end;
var
  tu:array[0..5000] of linetype;
  n,i:integer;
  c:char;
  a,b:longint;
  drawhead,now,newp,prev,temp:drawpoint;
  maxa,maxb,max:longint;
begin
  read(n);
  for i:=1 to n do
  begin
    read(tu[i].a);
    read(tu[i].b);
    read(c);
    readln(tu[i].color);
  end;
  tu[0].a:=0;
  tu[0].b:=1000000000;
  tu[0].color:='w';
  new(drawhead);
  drawhead^.a:=0;
  drawhead^.b:=1000000000;
  drawhead^.color:='n';
  drawhead^.next:=nil;
  for i:=n downto 0 do
  begin
    now:=drawhead;
    a:=tu[i].a;
    b:=tu[i].b;
    c:=tu[i].color;
    while (now<>nil) do
    begin
      if (now^.color='n') and (b>now^.a) and (a<now^.b) then
      begin
        break;
      end
      else
      begin
        if (b<now^.a) then
        begin
          now:=nil;
          break;
        end
        else
        begin
          prev:=now;
          now:=now^.next;
        end;
      end;
    end;

    while (a<b) and (now<>nil) do
    begin
      prev:=now;
      now:=prev^.next;
      if prev^.color='n' then
      begin
        if a>prev^.a then
        begin
          new(newp);
          newp^.a:=a;
          newp^.b:=prev^.b;
          newp^.color:='n';
          newp^.next:=now;

          prev^.b:=a;
          prev^.next:=newp;
          prev:=newp;
        end;
        if b<prev^.b then
        begin
          new(newp);
          newp^.a:=b;
          newp^.b:=prev^.b;
          newp^.color:='n';
          newp^.next:=prev^.next;

          prev^.b:=b;
          prev^.next:=newp;
          now:=newp;
        end;
        prev^.color:=c;
      end;
      a:=prev^.b;
    end;
  end;

  prev:=drawhead;
  now:=prev^.next;
  while (now<>nil) do
  begin
    if prev^.color=now^.color then
    begin
      prev^.b:=now^.b;
      prev^.next:=now^.next;
      dispose(now);
    end
    else prev:=now;
    now:=prev^.next;
  end;

  max:=0;
  now:=drawhead;
  while (now<>nil) do
  begin
    writeln(now^.a,' ',now^.b,' ',now^.color);
    if (now^.color='w') and (now^.b-now^.a>max) then
    begin
      max:=now^.b-now^.a;
      maxa:=now^.a;
      maxb:=now^.b;
    end;
    now:=now^.next;
  end;

  writeln(maxa,' ',maxb);
end.