Take care, it does not mean a closed interval.

As the subject says.

Also pay attention to the fact that according to the example - segment is (a;b]. I used this approach and got accepted. (O (N*N) btw :) )

Edited by author 11.11.2017 22:53

Edited by author 11.11.2017 22:53

First I got WA#11 . Found that a simple increase of size of array to 20005 gave AC #11.
Now I'm stuck in #15. Anyone have a case?

I've checked all the tests on the forum, but all of them actually wokred. What's wrong with the code?

type
Otrezok=record
  beginning,ending:real;
  colour:string;
end;

type
Point=record
  mean,predel:real;
end;

var
a:array[0..50000] of Otrezok;
b:array[0..50002] of Point;
i,N,j,s:integer;
k,j1,j2,max,f1,f2:real;
t,f3:string;

function colour(x:real;H:integer):string;
var j:integer;
begin

for j:=0 to H do
begin
if (x>=a[j].beginning) and (x<=a[j].ending) and (a[j].colour=' w') then colour:='w';
if (x>=a[j].beginning) and (x<=a[j].ending) and (a[j].colour=' b') then colour:='b';
end;
end;


begin

a[0].beginning:=0;
a[0].ending:=1000000000;
a[0].colour:=' w';
readln(N);
for i:=1 to N do
begin
readln(f1,f2,f3);
if f1<f2 then
begin
 a[i].beginning:=f1;
 a[i].ending:=f2;
 a[i].colour:=f3;
end;
end;
for j:=1 to N do
begin
b[j].predel:=0;
b[j+N].predel:=0;
b[j].mean:=a[j].beginning;
b[j+N].mean:=a[j].ending;
end;
b[0].predel:=0;
b[0].mean:=0;


  for i:=(2*N-1) downto 1 do
    for j:=1 to i do
    begin
        if b[j].mean>b[j+1].mean then
            begin
              k:=b[j+1].mean;
              b[j+1].mean:=b[j].mean;
              b[j].mean:=k;
            end;
       if (b[j].mean=b[j+1].mean) then b[j+1].mean:=0
       end;



for i:=1 to 2*N do
begin
if (b[i].mean<>0) and (colour(b[i].mean,N)<>colour(b[i].mean+0.1,N)) or (colour(b[i].mean,N)<>colour(b[i].mean-0.1,N)) then b[i].predel:=1;
if b[i].mean=0 then b[i].predel:=0;
end;
t:=colour(0,N);


s:=0;
for i:=0 to 2*N do
begin
if (b[i].predel=1) then
begin
s:=s+1;
k:=b[s].mean;
b[s].mean:=b[i].mean;
b[i].mean:=k;
end;
end;



for i:=s downto 0 do
b[i+1].mean:=b[i].mean;

b[s+2].mean:=1000000000;

max:=0;
b[0].mean:=0;


for i:=1 to s+2 do
begin
if t='w' then
begin
if (i mod 2)=0 then
begin
if (b[i].mean-b[i-1].mean)>max then
begin
max:=b[i].mean-b[i-1].mean;
j1:=b[i-1].mean;
j2:=b[i].mean;
end;
end;
end;
if t='b' then
begin
if (i mod 2)=1 then
begin
if b[i].mean-b[i-1].mean>max then
begin
max:=b[i].mean-b[i-1].mean;
j1:=b[i-1].mean;
j2:=b[i].mean;
end;
end;
end;
end;


write(Round(j1),' ',Round(j2));
end.

input ai bi C
it means that ->   line [ai, bi) is colored by C.

As described in the subject.

According to the segement discussion, re-paintings include [a,b] and we have to output (a,b),
So how the output for TEST1 is (47,634) ?
According to me the output should be (47,635) as 634 will be painted due to 3rd repainting.

what`s the meaning of segment? [a,b],(a,b),(a,b],or [a,b)?

Edited by author 18.04.2013 21:33

I understand that we are only concerned with the points mentioned, and not all the points between 1 and 10^9. After forming a segment tree and making all the updates, how can we find the longest white colored segment?

Thank you.

Try the following test:
50
3081 30488 b
16217 39416 w
7248 11364 w
17676 32492 w
25292 30974 w
1686 28199 w
9576 25807 w
18823 21457 w
30775 38642 w
7758 15847 b
6289 19805 b
1546 26246 w
27602 30148 w
9296 14836 w
19435 26471 w
27882 35227 w
24453 42158 w
943 1752 b
4080 12268 w
31529 41419 w
6238 22445 w
6262 13797 w
16616 31697 w
9990 12426 w
31675 46085 w
15149 32698 b
16029 18700 b
32372 50450 w
19642 25152 b
21096 30699 b
27244 35134 b
29951 43374 w
8869 9499 w
3375 28256 w
2060 14099 b
19972 37822 b
30222 33297 b
5433 9482 w
28735 54469 b
19053 31004 w
12234 27889 b
19117 19750 b
11927 17069 w
30056 32152 b
21756 25680 w
25656 44214 b
5308 18661 b
21710 26158 b
9196 32476 b
9917 11034 b

I don't know what the output is. Mine was 54496 1000000000

1.Pay attention 0 < ai < bi < 1e9. (I forgot the 0 and 1e9 axis...then wa teat 2 for many time)
2.The data of test 3 maybe
1
1 1000000000 b
answer：
0 1

I make an error while recursion to the leaf note. I return the l index instead of the axis it map to. T T

Edited by author 11.10.2012 19:04

Edited by author 27.09.2012 00:47

then the problem is clear

6
1 999999998 b
1 2 b
2 3 w
4 5 b
5 6 w
6 7 b

ans:
999999998 1000000000


Do you understand?

Compressing the coordinates is the most obvious solution and it's hard to name this approach "data structures"...

Can someone give hints on how to approach this problem? What data structures do I need? I can't find out how to apply Interval tree.