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
|
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 :) |
|
code_aim:
2017-07-01 19:48:26
0.01s |
| 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 |
RSS