SPOJ.com - Problem ARRAYSUB

ARRAYSUB - subarrays

#datastructures #sliding-window-1 #data-structure-1

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

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

(Edited: In fact, n <= 10^5)

print the output array

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

Output:
3 3 4 5 5 5 6

< Previous 14 15 16 17 18 19 20 21 22 23 24 Next >

	Amitayush Thakur: 2013-06-03 07:17:57 My code runs fine on http://ideone.com/ It works for all test cases I have given correct spacing between the output But still I am getting runtime error (NZEC) . Plz suggest me something.I have used Python 2.7 as programming language.
	vigneshwaran M: 2013-06-02 18:58:10 pls post tat 5th test case...
	Kumar Mrinal: 2013-05-27 16:38:59 Segment tree works fine ...
	!!AV!!: 2013-05-25 08:53:47 Little Modification to Range Minimum query and AC.. and yes there are spaces between the output numbers... :)
	Spar!k: 2013-05-20 22:53:11 set is enough
	Sudhanshu Shekhar: 2013-05-20 18:52:28 I got AC using Deque and Set but Segment Tree is timing out. Anyone any idea how to get around this? Last edit: 2013-05-20 18:52:55
	pankaj bhardwaj: 2013-05-17 12:58:36 can this be solved other than segmented tree ??
	Atul Kumar Verma: 2013-05-17 12:03:53 Finally AC after many TLE nice ques. :)
	Noob: 2013-05-16 21:13:33 Test case Pls :\| getting correct output for as many case given and plenty of random cases.no error of spaces. and what not. i am not getting AC
	natsu: 2013-05-13 03:55:53 used O(nk) with slight modifications got AC finally after 8 wa