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

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

where is my mistake?help!!
Послано zhujy 15 апр 2008 16:42
my program:

where is the problem?

program u1019;
type
 node=record
        l,r:longint; c:char
      end;
var
 ch,bk:char;
 n,k1,k2,len,i,j,ll,rr,ans,now,oi,oj:longint;
 a:array[1..100000]of node;
procedure add(l,r:longint; ch:char);
 begin
  inc(len);
  a[len].l:=l; a[len].r:=r; a[len].c:=ch;
 end;
function max(a,b:longint):longint;
 begin
  if a>b then exit(a)
  else exit(b);
 end;
function min(a,b:longint):longint;
 begin
 if a<b then exit(a)
 else exit(b)
 end;
procedure sort(l,r:longint);
 var  t:node;
  i,j,mid1,mid2,s:longint;
 begin
   i:=l; j:=r; s:=random(r-l+1)+l;
   mid1:=a[s].l;  mid2:=a[s].r;
   repeat
   while (a[i].l<mid1)or((a[i].l=mid1)and(a[i].r<mid2)) do inc(i);
   while (a[j].l>mid1)or((a[j].l=mid1)and(a[j].r>mid2)) do dec(j);
    if i<=j then begin
   t:=a[i]; a[i]:=a[j]; a[j]:=t;
   inc(i); dec(j)
    end;
   until i>j;
 if i<r then sort(i,r);
 if j>l then sort(l,j)
end;
begin
  readln(n); randomize;
  a[1].l:=0; a[1].r:=1000000000; a[1].c:='w'; len:=1;
  for i:=1 to n do begin
   readln(ll,rr,bk,ch);
  for j:=1 to len do begin
   if (a[j].l>rr)or(a[j].r<ll) then continue;
  if (ll<=a[j].l)and(a[j].r<=rr)then begin
    a[j].l:=ll; a[j].r:=rr; a[j].c:=ch;continue;  end;
    k1:=max(a[j].l,ll); k2:=min(a[j].r,rr);
   if a[j].l<k1 then add(a[j].l,k1,a[j].c);
   if a[j].r>k2 then add(k2,a[j].r,a[j].c);
    a[j].l:=ll; a[j].r:=rr; a[j].c:=ch;
    end;
  end;
  sort(1,len); ans:=0; now:=0;
  for i:=1 to len do begin
   if a[i].c='w' then if now=0 then begin
    now:=a[i].r-a[i].l+1; ll:=a[i].l end
  else inc(now,a[i].r-a[i].l+1);
   if a[i].c='b'then begin rr:=a[i].l;
   if now>ans then begin
    oi:=ll; oj:=rr; ans:=now end;
     now:=0;
   end;
   end;
  if (a[len].c='w')and(now>ans) then begin
   oi:=ll; oj:=1000000000 end;
  writeln(oi,' ',oj);
end.