Take care, it does not mean a closed interval. Thanks! I was confused about this before seeing your post. You lie. In problem segment is [ai, bi]. 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 :) ) Yes. Compressing coordinates and painting segments straightforwardly is enough. 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 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! 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 TRY to test this cases: INPUT 2 5 100 w 10 10 b OUTPUT 0 1000000000 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 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 875 98754 Edited by author 01.01.2009 12:08 thank you very much! but test#1 can never happy,because:0 < ai < bi < 109 what`s the meaning of segment? [a,b],(a,b),(a,b],or [a,b)? Edited by author 18.04.2013 21:33 Segment is [a,b] (for painting). But you must output interval (a,b) Edited by author 01.08.2013 18:13 Edited by author 01.08.2013 18:13 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 |
|