Sphere Online Judge

SPOJ Problem Set (classical)

10582. subarrays

Problem code: ARRAYSUB


Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.

Input

the number n denoting number of elements in the array then after a new line we have the numbers of the array

and then k in a new line

n<10^6

k<10^5

1 <= k <=n

and each element of the array is between 0 and 10^6

Output

print the output array

Example

Input:
9
1  2  3  1  4  5  2  3  6
3
Output:
3 3 4 5 5 5 6


Added by:priyamehtanit
Date:2012-02-09
Time limit:1s-4s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:own

hide comments
2014-04-14 20:33:59 free mind ;)
done in 0.09 with O(n*k) finally !
2014-03-02 18:26:46 Vlad Mosko
NlogN is really easy.
2014-01-11 21:13:53 appy
anyone help with the whitespaces in input
e.g
9
<--- this white space
1 2 3 1 4 5 2 3 6
please and is there space or \n after the last output?????
2014-01-11 17:10:55 appy
is there any whitespace means after
9
<--- this line
i m getting wrong answer again and again...please sum1 help
2014-01-05 21:06:00 shashank
Interesting Same implementation in java got NZEC but in C++ got AC ....
Sometimes java sucks ....
2013-12-31 15:32:09 pika_pika
those who are getting WA in the 5th test case try cases with k = 1
eg
5
2 8 4 3 6
1
worked for me considering this.
2013-12-16 23:37:14 Ashish
Got TLE with O(nk)... finally AC .. phew!!!
2013-12-14 10:43:40 SanchitK
getting WA in 5th test case
2013-12-08 15:27:33 anonymous
o(n) soln runs slower than o(n*k)
Mostly because of STL
2013-12-08 04:27:25 ~!(*(@*!@^&
There are problems if you read input by a fast in/out procedure. It costs many WAs.

Last edit: 2013-12-08 04:59:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.