Discussion @ 1019. Line Painting @ Timus Online Judge

Simonenko Vladislav Complexity:O(N*LOG(N)),TIME:0,031 sec WHO IS BETTER??? [10] // Problem 1019. Line Painting 5 Jun 2004 15:03

Complexity:O(N*LOG(N)),TIME:0,031 sec WHO IS BETTER???

Тёма и Серёжа Re: Complexity:O(N*LOG(N)),TIME:0,031 sec WHO IS BETTER??? // Problem 1019. Line Painting 7 Jun 2004 20:02

Complexity:O(0),TIME:0 sec

KRSU 2 Re: Complexity:O(N*LOG(N)),TIME:0,031 sec WHO IS BETTER??? // Problem 1019. Line Painting 28 Feb 2005 13:16

Can you tell me the idea how to solve the problem
in O(n*log(n)) ?

Vlad Veselov [PMG17,Vinnitsa - KNU,Kiev] 0.015 [5] // Problem 1019. Line Painting 28 Feb 2005 16:25

770478 15:56:13
28 фев 2005 TECTOBOP 1019 Pascal Accepted
0.015 339 КБ

Vlad Veselov [PMG17,Vinnitsa - KNU,Kiev] And it is O(N*N) ;) [4] // Problem 1019. Line Painting 5 Mar 2005 06:07

BYF Using fillchar can make it very fast. [3] // Problem 1019. Line Painting 5 Mar 2005 07:32

Ves I don't think so. It's just O(N). [2] // Problem 1019. Line Painting 6 Mar 2005 05:24

BYF How does it work? [1] // Problem 1019. Line Painting 6 Mar 2005 08:21

Ves What works? Prog itself is O(N*N), but block, which can be replaced with FillChar, is just O(N). // Problem 1019. Line Painting 8 Mar 2005 04:20

Fu Dong Time: 0.015 sec [1] // Problem 1019. Line Painting 8 Apr 2005 15:58

816394 15:41:20
8 апр 2005 Fu Dong 1019 Pascal Accepted
0.015 660 K

My complexity is O(N^2), but I used Hash Table ,so the Time is 0.015 sec.

KingPin Re: Time: 0.015 sec // Problem 1019. Line Painting 17 May 2005 00:22

849412 00:19:10

17.05.2005 KingPin 1019 Pascal Accepted

0.015 173 КБ

I used Cartesian tree. So, complexity is O(n*log(n))

Discussion of Problem 1019. Line Painting