Problem statement:
You are given a deque container with a specified number of integers. You need to process Q queries, where each query consists of a single character followed by an integer. There are two types of queries:
'1 X': Insert the element X at the back of the deque.
'2': Remove the element from the front of the deque.
Your task is to process the queries and print the maximum element in the deque after each '2' query.
Sample Input:
The first line of input contains an integer T, representing the number of test cases.
Each test case consists of two lines:
The first line contains two space-separated integers, N and K, where N is the number of elements in the deque and K is the number of queries.
The second line contains N space-separated integers, denoting the elements of the deque.
2
6 4
1 2 3 4 5 6
5 2
3 4 6 5 8
Sample Output:
For each '2' query, print the maximum element in the deque on a new line.
6
5
Explanation:
In the first test case, we have a deque with 6 elements: {1, 2, 3, 4, 5, 6}. We process 4 queries as follows:
Query 1: '1 X'. We insert the element X = 7 at the back of the deque. The deque becomes {1, 2, 3, 4, 5, 6, 7}.
Query 2: '2'. We remove the element from the front of the deque, which is 1. The deque becomes {2, 3, 4, 5, 6, 7}. The maximum element is 7.
Query 3: '1 X'. We insert the element X = 8 at the back of the deque. The deque becomes {2, 3, 4, 5, 6, 7, 8}.
Query 4: '2'. We remove the element from the front of the deque, which is 2. The deque becomes {3, 4, 5, 6, 7, 8}. The maximum element is 8.
In the second test case, we have a deque with 5 elements: {3, 4, 6, 5, 8}. We process 2 queries as follows:
Query 1: '2'. We remove the element from the front of the deque, which is 3. The deque becomes {4, 6, 5, 8}. The maximum element is 8.
Query 2: '2'. We remove the element from the front of the deque, which is 4. The deque becomes {6, 5, 8}. The maximum element is 8.
#include <iostream>
#include <deque>
using namespace std;
void printMaxOfK(deque& dq, int k) {
int maxVal = dq.front();
for (int i = 1; i < k; i++) {
if (dq[i] > maxVal)
maxVal = dq[i];
}
cout << maxVal << endl;
}
void processQueries(int n, int k, deque& dq) {
for (int i = 0; i < n; i++) {
int x;
cin >> x;
dq.push_back(x);
if (i >= k - 1)
printMaxOfK(dq, k);
if (dq.size() == k)
dq.pop_front();
}
}
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
deque dq;
processQueries(n, k, dq);
}
return 0;
}
Code Explanation
The printMaxOfK function takes a deque dq and an integer k as input. It iterates over the first k elements of the deque to find the maximum value. The maximum value is stored in the variable maxVal and printed at the end.
The processQueries function takes the number of elements n, the number of queries k, and the deque dq as input. It iterates n times to process each query.
Inside the loop, it reads an integer x from input and inserts it at the back of the deque using dq.push_back(x).
If the current index i is greater than or equal to k - 1, it calls the printMaxOfK function to print the maximum value of the last k elements in the deque.
If the size of the deque is equal to k, it removes the element from the front of the deque using dq.pop_front().
In the main function, it reads the number of test cases t from input and starts a loop to process each test case.
Inside the loop, it reads the values of n and k for the current test case.
It initializes a deque dq to store the elements of the deque for the current test case.
It calls the processQueries function to process the queries for the current test case.
Finally, the program ends and returns 0.
The provided solution reads the input, processes the queries, and prints the maximum element after each '2' query. It follows the given format and provides the expected output.
Please note that this code is designed for the specific problem "Deque-STL" on Hackerrank and may not work correctly for other similar problems or different input formats.