|
|
back to boardIt can be solve in O(N+M) Posted by Ted 7 May 2004 13:08 Can you tell more about this solution? Re: Can you tell more about this solution? Posted by Ted 7 May 2004 20:29 I'm not good at English.
A[I] is the Ith number.
First,try to count a array F.
F[I] means the nearest number A[F[I]]:
A[F[I]]>A[I] and F[I]>I.
You can count F in O(N).
Find largest number in [L,R],just find a min I,F[I]>R.
So you can solve the problem in O(N+M).
And this problem is RMQ problem, also have a very hard standard solution in O(N+M).
Edited by author 07.05.2004 20:31 Re: Can you tell more about this solution? Posted by bug27 30 Mar 2005 18:37 strong! Re: Can you tell more about this solution? Good idea. But I had to be very carefully solving it.
Edited by author 04.05.2006 20:00 Re: It can be solve in O(N+M) There is an interesting situation here: when I declared arrays a and f with size 1..25000, I got WA#2. When I changed them to 1..25001, I got AC... Re: It can be solve in O(N+M) I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. Re: It can be solve in O(N+M) Posted by Mewtwo 20 Mar 2016 18:58 I have used rather simple method, I have organized four stacks, first two to make a queue of M size, and others to store max elements of queue, by this way you can find elements in constant time. Very useful for Java, you have Class Stack. Thanks for sharing the idea... :) Re: Can you tell more about this solution? Posted by c_pp 8 Jan 2017 01:27 Thanks, @Ted.
Your idea is brilliant.
I count F[] array with O(N) , used stack.
+ buffered i/o ==> result is very good: AC. 0.001s |
|
|
