I've tried many test data.But I always got wa on test data 8.

Here is my code.
And I'm sorry for my bad English- -!
Waiting for your data! Thanks very much!


program ural1019_3;
var
  fill:array [1..5000,1..3] of longint;
  point:array [1..10003] of longint;
  col:array [1..10002] of byte;
  a,i,d,n,la,nn,x,y,u,yy:longint;
  c:char;

procedure qsort(l,r:integer);
var i,j,x,y:longint;
begin
     i:=l;j:=r;x:=point[(l+r) div 2];
     repeat
           while point[i]<x do inc(i);
           while point[j]>x do dec(j);
           if i<=j then begin
              y:=point[i];point[i]:=point[j];point[j]:=y;
              inc(i);dec(j);
           end;
     until i>j;
     if l<j then qsort(l,j);
     if i<r then qsort(i,r);
end;

procedure work;
var
  a,i,b,ll,max,lr,ml,mr:longint;

  function x2find(p:longint):integer;
  var a,l,r,x:longint;
  begin
    l:=1;r:=nn;
    while l<r do begin
          x:=point[(l+r) div 2];
          if p=x then break;
          if p<x then r:=(l+r) div 2-1;
          if p>x then l:=(l+r) div 2+1;
    end;
    x2find:=(l+r) div 2;
  end;

begin
  for a:=1 to nn-1 do col[a]:=1;
  for a:=1 to n do begin
      i:=x2find(fill[a,1]);
      for b:=i to nn-1 do if point[b]<>fill[a,2] then col[b]:=fill[a,3] else break;
  end;
  max:=0;a:=1;
  while a<nn do begin
        while (col[a]=2) and (a<=nn-1) do inc(a);
        if a=nn then break;
        ll:=point[a];
        while (col[a]=1) and (a<=nn-1) do inc(a);
        lr:=point[a];
        if lr-ll>max then begin max:=lr-ll; ml:=ll; mr:=lr; end;
  end;
  if n<=0 then writeln('0 1000000000') else writeln(ml,' ',mr);
end;

begin
  readln(n);u:=n;
  for a:=1 to u do begin
      read(x,y,c);
      while (c<>'w') and (c<>'b') do read(c);
      readln;
      if x>y then begin yy:=x; x:=y; y:=yy; end;
      if x=y then begin dec(n); continue; end;
      fill[a,1]:=x; fill[a,2]:=y;
      point[a*2-1]:=fill[a,1];point[a*2]:=fill[a,2];
      if c='w' then fill[a,3]:=1 else fill[a,3]:=2;
  end;
  point[n*2+1]:=0;point[n*2+2]:=1000000000;
  qsort(1,n*2+2);
  la:=1;i:=2;
  while i<n*2+2 do begin
        while (point[i]=point[la]) and (i<=n*2+2) do inc(i);
        if i>n*2+2 then break;
        inc(la);
        point[la]:=point[i];
  end;
  nn:=la;
  work;
end.

Edited by author 27.07.2007 20:54

O my god.I checked it for 2 hours.Finally I found where I was wrong.

Here is the data which showed me I was wrong.

11
1 999999999 b
5175 8925 b
2844 6891 w
1820 3903 b
8978 8978 b
4663 6345 w
316 1072 w
3197 7933 w
4124 4725 b
2832 3401 w
663 5756 w

Correct answer is:316 7933
Hope it can help you.
And sorry for my terrible English again.

Edited by author 27.07.2007 22:46

Edited by author 31.07.2007 09:56

a very useful testcase indeed!

so thx!