Brief description:
。。维护一个宽度为 k 的滑动窗口。。分别统计所有位置的最大值和最小值。。
Analysis:
1. C++ 怎么都过。 / G++ 怎么都 TLE 。。
2. “那些500-600MS的代码到底是怎么弄出来的。。”。。
.. .
const int N = 1000009;
int a[N], q[N], cz, op;
int n, k;
template<class T> void gao(T cmp){
cz = 0, op = -1; REP_1(i, k){
while (cz <= op && cmp(a[i], a[q[op]])) --op;
q[++op] = i;
}
printf("%d ", a[q[cz]]);
FOR_1(i, k + 1, n){
if (q[cz] == i - k) ++cz;
while (cz <= op && cmp(a[i], a[q[op]])) --op;
q[++op] = i; printf("%d ", a[q[cz]]);
}
puts("");
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
RD(n, k); REP_1(i, n) RD(a[i]);
gao(less<int>()), gao(greater<int>());
}
External link:
http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=16694
