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 1019. Line Painting

where is my mistake?help!!
Posted by zhujy 15 Apr 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.