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-08-14 20:56:29 Aradhya
why my O(3n) soln is taking so much time ;/

Last edit: 2014-08-14 20:56:46
2014-07-22 12:05:44 VirinchiSamineni
got WA in 5th case can somebody help with this issue
2014-07-16 22:31:02 (Tjandra Satria Gunawan)(曾毅昆)
I don't know O(n) solution for this problem yet, but my O(n*log n),[using binary search] is 0.03s :-P
2014-07-16 20:45:02 zicowa
Hello Coders !!
I know you all are doing great !!
O(nlog(n)) solution can be easily think for this problem sets/priority queue/ segment tree but there exists a O(n) solution for this problem think for O(n) solution you will surely learn something my last submission is on the same algo . and you dont believe it is the smallest code among all :D
2014-07-01 08:43:30 Saurav Sharma
brute force method get rejected
2014-06-30 02:49:03 Simarpreet Singh
wow solved with segmented tree :)

Last edit: 2014-06-30 02:58:47
2014-06-24 22:36:55 Abhishek Gupta
My 50th...
map to the rescue
2014-06-10 17:23:07 saikrish
pls check my code 11735455 @ priyamehtanit
2014-06-08 08:14:55 surayans tiwari
geting WA in 5th case
5
2 8 4 3 6
1
tried this got 28436
help!
2014-05-31 15:57:02 Ashish Gaurav
Good Question! O(n*k) definitely works, but remember not to make your code O(n*k) for all cases. It should be worst case O(n*k).
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.