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 1418. Military Story

How to get AC in 0.1 s or less ?
Posted by N.M.Hieu ( DHSP ) 12 Jun 2006 17:27
I've got AC but my run time is 0.765s . I saw that some people got AC with little run time so I think there's another solution better than using Graham k times ( k = maximal possible number of fences ).
If it's true , please tell me your solution.
Thank you very much.
My e-mail : hard7771988@yahoo.co.uk
Re: How to get AC in 0.1 s or less ?
Posted by Igor Dex 22 Jun 2006 13:25
To solve this problem efficiently we have to use Chazelle's algorith which is O(n log n). Sometimes it's called "onion peeling algorithm". But I can't find this algorithm in the net. If someone knows , please tell us links to it.
Re: How to get AC in 0.1 s or less ?
Posted by TheBeet 21 Aug 2006 11:14
 TheBeet 1418 C++ Accepted
 0.093 206 KB

I use Graham k times. My solution is O(n^2)