ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1491. Unreal Story

TLE
Posted by Daniel 14 Oct 2006 15:37
TLE №18
Can you please give me any hint?
Re: TLE
Posted by Victor Barinov (TNU) 14 Oct 2006 16:52
Try to find algo O(n^(3/2)) or O(n log n )
Re: TLE
Posted by Ostap Korkuna (LNU) 15 Oct 2006 01:40
The best solution is O(n). Try to find it.
Re: TLE
Posted by Victor Barinov (TNU) 15 Oct 2006 02:42
O(n) ????  Are your sure???
Strange that fastest solution works in 0.125 seconds...
Re: TLE
Posted by Yosif Yosifov 15 Oct 2006 18:24
O(N) is without using any kind of tree , right ? Can I get a hint to this solution? ( I have already solved the problem .. )
Re: TLE
Posted by HASK 15 Oct 2006 19:52
I got a AC, thx.
Re: TLE
Posted by Begemot 16 Oct 2006 17:30
Please, advice me how to solve this problem? Using binary tree? Thank you.
O(N) solution is very simple. Just two loops! (-)
Posted by Vladimir Yakovlev (USU) 16 Oct 2006 20:07
Re: O(N) solution is very simple. Just two loops! (-)
Posted by Daniel 16 Oct 2006 20:32
I have found this O(N) solution! Just 1 minute thinking.
It is really very easy.
Thank you very much. If I didnt know that there is such solution I would hardly find it :)
Re: TLE
Posted by KIRILL(ArcSTU) 16 Oct 2006 22:23


Edited by author 17.10.2006 02:22
Re: O(N) solution is very simple. Just two loops! (-)
Posted by sniper 9 Feb 2007 11:40
From left and from right(Because b>=a).
That's the two loops?!

poor English...