Discussion @ 1019. Line Painting @ Timus Online Judge

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

Posted by Simonenko Vladislav 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???

Posted by Тёма и Серёжа 7 Jun 2004 20:02

Complexity:O(0),TIME:0 sec

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

Posted by KRSU 2 28 Feb 2005 13:16

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

0.015

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

And it is O(N*N) ;)

Using fillchar can make it very fast.

Posted by BYF 5 Mar 2005 07:32

I don't think so. It's just O(N).

Posted by Ves 6 Mar 2005 05:24

How does it work?

Posted by BYF 6 Mar 2005 08:21

What works? Prog itself is O(N*N), but block, which can be replaced with FillChar, is just O(N).

Posted by Ves 8 Mar 2005 04:20

Time: 0.015 sec

Posted by Fu Dong 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.

Re: Time: 0.015 sec

Posted by KingPin 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