rt

input:
10 3
-94 21 24 73 38 77 11 73 9 -88 

output:
-94 21 24 38 11 11 9 -88 
24 73 73 77 77 77 73 73 

code

#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;
struct dig {
public:
	int xb, sz;
	bool operator<(dig n) { return this->sz < n.sz; }
	bool operator>(dig n) { return this->sz > n.sz; }
};
deque<dig>q1,q2;
vector<int>da1, da2;
int main() {
	ios::sync_with_stdio(0);
	int n, k;
	cin >> n >> k;
	vector<dig>vec(n);
	for (int i = 0; i < n; i++)vec[i].xb=i,cin >> vec[i].sz;
	for (int i = 0; i < k; i++) {
		while (!q1.empty() && vec[i] < q1.back())q1.pop_back();
		q1.push_back(vec[i]);
		while (!q2.empty() && vec[i] > q2.back())q2.pop_back();
		q2.push_back(vec[i]);
	}
	for (int i = k; i < n; i++) {
		da1.push_back(q1.front().sz);
		while (!q1.empty() && vec[i] < q1.back())q1.pop_back();
		q1.push_back(vec[i]);
		while (!q1.empty() && q1.front().xb <= i-k)q1.pop_front();
		da2.push_back(q2.front().sz);
		while (!q2.empty() && vec[i] > q2.back())q2.pop_back();
		q2.push_back(vec[i]);https://www.luogu.com.cn/image
		while (!q2.empty() && q2.front().xb <= i-k)q2.pop_front();
	}
	da1.push_back(q1.front().sz);
	da2.push_back(q2.front().sz);
	for (int i = 0; i < da1.size(); i++)cout << da1[i] << " ";
	putchar('\n');
	for (int i = 0; i < da2.size(); i++)cout << da2[i] << " ";
	return 0;
}