The problem asks us to find the maximum values for each subarray of size and then print the minimum of these maximums. The main problem is to keep track of the maximum elements for each subarray of size . Using a deque can easily solve this problem for us.
For each query, we get an integer , and we’ll try to maintain a deque of size where it contains the maximum element at one of its ends. We slide over the array, keeping a window of size .
Pretend we are at index , and the maximum element is at the end of the deque. When we add the element, we first delete all the elements from the deque that do not fall within the current window of size . Then, we delete those elements that are less than the element and push it accordingly so that the maximum element of this window is at the end of the deque.
We maintain the answer by taking the minimum of the answer with the maximum value for each subarray for a particular and print it at the end when all the subarrays are processed.
C++ code-
#include
#include
#include
using namespace std;
const int N = 1e5 + 100;
int a[N];
deque dq;
int main() {
int n, cq;
scanf(" %d %d", &n, &cq);
for (int i = 0; i < n; i++) {
scanf(" %d", a + i);
}
for (int it = 0; it < cq; it++) {
int d;
scanf(" %d", &d);
dq.clear();
int best = 1 <= d - 1) {
assert(dq.size());
if (best > a[dq.front()]) {
best = a[dq.front()];
}
}
}
printf("%d\n", best);
}
return 0;
}