ARRAYSUB - subarrays
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
Time limit should be reduced!! Optimised Brute force also getting AC!
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
simple idea of arrays and selection sort is enough to solve the problem.
Using Deque with fast i/o gives u AC with 0.00s time . But Also solve it with segment trees etc :)
easily solved using set and map...
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
What is definition for contiguous subarray in this case?
Compilation error-->AC :)