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

Program p1019;

Const MaxN = 6000;

Var S : Array[1..MaxN, 1..2]of Longint;
    Del : Array[1..MaxN]of Byte;
    N, s0, ai, bi : Longint;
    ci : Char;

Procedure Check;
Var i, j, k : Longint;
  begin
    k := 0;
    for i := 1 to s0 do begin
      if i > s0 - k then break;
      if (Del[i] = 1) or (S[i, 1] = S[i, 2]) then begin
        k := k + 1;
        for j := i to s0 - 1 do
          S[j] := S[j + 1];
      end;
    end;
    s0 := s0 - k;
  end;

Procedure Black;
Var i, ts0 : Longint;
  begin
    FillChar(Del, SizeOf(Del), 0);
    ts0 := s0;
    for i := 1 to s0 do
      if (ai <= S[i, 1]) and (bi >= S[i, 1]) and (bi <= S[i, 2]) then
        S[i, 1] := bi else
      if (ai >= S[i, 1]) and (ai <= S[i, 2]) and (bi >= S[i, 2]) then
        S[i, 2] := ai else
      if (ai <= S[i, 1]) and (bi >= S[i, 2]) then
        Del[i] := 1 else
      if (ai >= S[i, 1]) and (bi <= S[i, 2]) then begin
        ts0 := ts0 + 1;
        S[ts0, 1] := bi;
        S[ts0, 2] := S[i, 2];
        S[i, 2] := ai;
      end;
    s0 := ts0;
    Check;
  end;

Procedure Merge;
Var i, j : Longint;
    ex : Boolean;
  begin
    FillChar(Del, SizeOf(Del), 0);
    While True do begin
      ex := true;
      for i := 1 to s0 - 1 do
        if Del[i] = 0 then
          for j := i + 1 to s0 do
            if Del[j] = 0 then
              if (S[i, 1] <= S[j, 1]) and (S[i, 2] >= S[j, 1]) then
begin
                if S[j, 2] > S[i, 2] then S[i, 2] := S[j, 2];
                Del[j] := 1;
                ex := false;
              end else
              if (S[i, 1] <= S[j, 2]) and (S[i, 2] >= S[j, 2]) then
begin
                if S[j, 1] <= S[i, 1] then S[i, 1] := S[j, 1];
                Del[j] := 1;
                ex := false;
              end else
              if (S[i, 1] >= S[j, 1]) and (S[i, 2] <= S[j, 2]) then
begin
                Del[i] := 1;
                ex := false;
              end else
              if (S[j, 1] >= S[i, 1]) and (S[j, 2] <= S[i, 2]) then
begin
                Del[j] := 1;
                ex := false;
              end;
      if ex then break;
    end;
  end;

Procedure WriteIt;
Var L, R, i : Longint;
  begin
    L := 0; R := 0;
    for i := 1 to s0 do
      if (S[i, 2] - S[i, 1] > R - L) or
         ((S[i, 2] - S[i, 1] = R - L) and (S[i, 1] < L)) then begin
        L := S[i, 1];
        R := S[i, 2];
      end;
    Writeln(L, ' ', R);
  end;

begin
  S[1, 1] := 0; S[1, 2] := 1000000000;
  s0 := 1;
  Readln(N);
  While N > 0 do begin
    N := N - 1;
    Readln(ai, bi, ci, ci);
    if ai >= bi then Continue;
    if ci = 'b' then
      Black
    else begin
      s0 := s0 + 1;
      S[s0, 1] := ai;
      S[s0, 2] := bi;
    end;
  end;
  Merge;
  WriteIt;
end.
Pursue Success Try this test. [10] // Problem 1019. Line Painting 5 May 2003 20:30
INPUT:
14
1 999999999 b
1 300 b
20 120 w
1 50 b
220 300 w
250 270 b
40 70 w
50 160 b
30 90 w
120 140 w
40 50 b
180 200 w
1 40 w
70 80 w

OUTPUT:
0 40

Hope it can help.If still not,I can give you more test data.
Frick Re: Try this test. [5] // Problem 1019. Line Painting 17 Aug 2004 14:38
my program made the correct answer for the test case above, but WA at #2 on the judge, could you give me some more tests? Thank you very much!
bluebird Try This Test ;) [4] // Problem 1019. Line Painting 4 Sep 2004 00:00
input
9
2 34 w
1 95 b
33 875 b
34 543 w
33 762 b
98754 999999843 b
87 221 w
76 432 w
325 764 b

output
76 325

if you want more test mail me
Hanieh_Mirzaei@yahoo.com
xu xiao tao Re: Try This Test ;) [2] // Problem 1019. Line Painting 30 Sep 2004 15:00
I thought your test is incorrect.
I solve it by hand and I found the answer should be
875 98754,isn't it?
thwomass Re: Try This Test ;) [1] // Problem 1019. Line Painting 24 Feb 2005 17:57
I have the same problem (WA on #2). I checked this test and it sould be 875 98754. why is it 76 325 ??
Liu Guyue Re: Try This Test ;) // Problem 1019. Line Painting 27 Nov 2005 20:43
...well i also wa on test 2

but  the 1st test my answer is 60 140
 the 2nd the same as upstairs

i'm wa on test 8 now ...

Edited by author 27.11.2005 20:47

Edited by author 27.11.2005 20:48

Edited by author 27.11.2005 20:49
Ca Ca Re: Try This Test ;) // Problem 1019. Line Painting 25 Apr 2012 11:28
xuyiwen Re: Try this test. // Problem 1019. Line Painting 30 Nov 2006 15:04
thanks very much for your test date,because of then test date,i found what is wrong with my program
edward Re: Try this test. [1] // Problem 1019. Line Painting 29 Jan 2007 17:12
14
1 999999999 b
1 300 b
20 120 w
1 50 b
220 300 w
250 270 b
40 70 w
50 160 b
30 90 w
120 140 w
40 50 b
180 200 w
1 40 w
70 80 w
The answer isn't
50 90?

Where did it say that 0 is white?
Marc Re: Try this test. // Problem 1019. Line Painting 19 May 2012 22:23
Edward, I think in this test 1 40

Edited by author 19.05.2012 22:24
code_code Re: Try this test. // Problem 1019. Line Painting 8 May 2012 16:21
Hi,
I have tried out many tests and they are all passing.
However, I get "Wrong answer" in test #1 and stuck up there.

Can u give me test cases for test #1 ?