【To loog on line1】抱灵我谔谔

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;
}