ARRAYSUB - subarrays
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
(Edited: In fact, n <= 10^5)
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
hide comments
sophozaar:
2018-01-13 11:50:24
Time limit should be reduced!! Optimised Brute force also getting AC! |
|
shub1025:
2017-12-28 17:44:11
10
|
|
dunjen_master:
2017-12-27 21:16:42
make sure you write s.erase(s.find(a[i-k])) where s is a multiset otherwise all the occurences of a[i] will be deleted...costed me a WA |
|
dsri_99:
2017-12-23 06:30:25
simple idea of arrays and selection sort is enough to solve the problem.
|
|
karthik1997:
2017-12-16 19:48:25
Using Deque with fast i/o gives u AC with 0.00s time . But Also solve it with segment trees etc :) |
|
arjun8115:
2017-10-06 07:29:24
easily solved using set and map... |
|
hitman007:
2017-09-25 21:01:59
I can see lots of people using deque and segment tree. You can try to implement it using sparse table as well (although not best example of it) https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Sparse_Table_(ST)_algorithm |
|
mahilewets:
2017-09-05 15:40:56
std::multiset |
|
hwojtowicz:
2017-08-23 09:58:50
What is definition for contiguous subarray in this case?
|
|
raichu7:
2017-07-30 03:46:37
Compilation error-->AC :) |
Added by: | priyamehtanit |
Date: | 2012-02-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | own |