Bianca_ @ 2018-07-19 20:35:19
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
int head=1,tail=1;
struct node{
int num,tag;
};
node a[1000010],q[1000010];
inline void pop_front(){
head++;
return;
}
inline void pop_back(){
tail--;
return;
}
inline void push(node x){
q[tail].num=x.num;
q[tail].tag=x.tag;
tail++;
return;
}
inline bool q_empty(){
return head==tail;
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].num);
a[i].tag=i;
}
for(int i=1;i<=n;i++){
for(int j=tail-1;j>=1;j--) if(!q_empty()&&q[j].num>=a[i].num) pop_back();
push(a[i]);
while(q[head].tag<=a[i].tag-k) pop_front();
if(i>=k) printf("%d ",q[head].num);
}
printf("\n");
head=1,tail=1;
for(int i=1;i<=n;i++) q[i].num=0,q[i].tag=0;
for(int i=1;i<=n;i++){
for(int j=tail-1;j>=1;j--) if(!q_empty()&&q[j].num<=a[i].num) pop_back();
push(a[i]);
while(q[head].tag<=a[i].tag-k) pop_front();
if(i>=k) printf("%d ",q[head].num);
}
return 0;
}
by Bianca_ @ 2018-07-19 20:38:45
而且诡异的是T了第二个点 然而下了数据之后 答案秒出???