Show all threads Hide all threads Show all messages Hide all messages |
"The segment of numerical axis from 0 to 10^9 is painted into white color." means[0, 10^9). | some_programming_novice | 1019. Line Painting | 15 Nov 2018 10:25 | 1 |
Take care, it does not mean a closed interval. |
ATTENTION ! input and output is as follows [ai,bi). It means that the point ai is white but the point bi maybe not white | Phan Hoài Nam - Đại học Ngoại ngữ Tin Học TP.HCM | 1019. Line Painting | 22 Aug 2018 14:19 | 3 |
Thanks! I was confused about this before seeing your post. You lie. In problem segment is [ai, bi]. |
Is the point 1e9 painted white initially? | Myrcella | 1019. Line Painting | 22 Aug 2018 08:43 | 1 |
|
The problem is easily solvable without segment tree. | Jorres | 1019. Line Painting | 21 Jul 2018 14:54 | 2 |
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. |
No subject | Jorres | 1019. Line Painting | 11 Nov 2017 22:51 | 1 |
Edited by author 11.11.2017 22:53 |
No subject | Jorres | 1019. Line Painting | 11 Nov 2017 22:51 | 1 |
Edited by author 11.11.2017 22:53 |
Any test data can help me? Always WA..I'm getting crazy! Thx! | Artanis | 1019. Line Painting | 16 Apr 2017 21:42 | 4 |
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! |
If you want more fast code submit your solution to night , really :))) | c_pp | 1019. Line Painting | 20 Dec 2016 02:37 | 1 |
|
WA #15 | encrypted_swordsmen | 1019. Line Painting | 10 Oct 2016 12:20 | 1 |
WA #15 encrypted_swordsmen 10 Oct 2016 12:20 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? |
WA 11 | Ilya | 1019. Line Painting | 30 Jan 2015 09:55 | 1 |
WA 11 Ilya 30 Jan 2015 09:55 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. |
Be careful. Test 2 and Test 3 | Adhambek | 1019. Line Painting | 11 Dec 2014 08:00 | 1 |
input ai bi C it means that -> line [ai, bi) is colored by C. |
tips on wa at test 13 | uuau99999 | 1019. Line Painting | 14 Apr 2014 09:53 | 1 |
As described in the subject. |
Help in TEST1 Output | chang | 1019. Line Painting | 3 Jan 2014 06:34 | 1 |
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.
|
one question , WA 9 | Tbilisi SU: Davit Rachvelishvili(rachvela) | 1019. Line Painting | 8 Nov 2013 12:42 | 5 |
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? | 95487701 | 1019. Line Painting | 1 Aug 2013 18:11 | 2 |
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 |
How to do this problem using segment trees? | Pushkar Mishra | 1019. Line Painting | 14 Mar 2013 11:30 | 1 |
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. |
If you get Crash (access violation) | Berendea | 1019. Line Painting | 8 Jan 2013 05:48 | 1 |
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 |
Tips of WA3 and WA2 | h2952220 | 1019. Line Painting | 11 Oct 2012 19:01 | 1 |
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 |
CE | ONU_1785 | 1019. Line Painting | 27 Sep 2012 00:43 | 1 |
CE ONU_1785 27 Sep 2012 00:43 Edited by author 27.09.2012 00:47 |
The meaning of "open segment" is (a, b]. Every segment in the statement is in that format.... | yefllower | 1019. Line Painting | 31 Aug 2012 15:47 | 1 |
then the problem is clear |