WA_automat @ 2022-06-24 21:19:42
#include<iostream>
#include<deque>
using namespace std;
int n, k, a[100005];
class MyQueue_big {
public:
deque<int> que;
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
void push(int value) {
while (!que.empty() && value > que.back()) {
que.pop_back();
}
que.push_back(value);
}
int front(void) {
return que.front();
}
};
class MyQueue_small {
public:
deque<int> que;
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
void push(int value) {
while (!que.empty() && value < que.back()) {
que.pop_back();
}
que.push_back(value);
}
int front(void) {
return que.front();
}
};
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
MyQueue_small small;
MyQueue_big big;
for (int i = 0; i < k; ++i) {
small.push(a[i]);
big.push(a[i]);
}
cout << small.front() << ' ';
for (int i = k; i < n; ++i) {
small.pop(a[i - k]);
small.push(a[i]);
cout << small.front() << ' ';
}
cout << endl;
cout << big.front() << ' ';
for (int i = k; i < n; ++i) {
big.pop(a[i - k]);
big.push(a[i]);
cout << big.front() << ' ';
}
cout << endl;
return 0;
}
by Fla_Akebono @ 2022-07-14 15:39:40
考虑一下数组a开小了
n<100,000