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

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

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.

if there is a test like this
"5 100 w"
does it mean that both points 5 and 10 are colored in white?
or only points betwen them.
can somebody give me test, I have WA 9

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