biophitma_wby @ 2024-10-26 09:02:38
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,k,a[N];
int queue_min[N],head_min=1,rear_min=0;
int queue_max[N],head_max=1,rear_max=0;
int main(){
scanf("%d%d%d",&n,&k,&a[1]);
rear_min++;
queue_min[rear_min]=1;
rear_max++;
queue_max[rear_max]=1;
for(int i=2;i<=n;i++){
scanf("%d",&a[i]);
if(i<=k){
while(a[i]<a[queue_min[head_min]]&&head_min<=rear_min)rear_min--;
rear_min++;
queue_min[rear_min]=i;
}
if(i<=k){
while(a[i]>a[queue_max[head_max]]&&head_max<=rear_max)rear_max--;
rear_max++;
queue_max[rear_max]=i;
}
}
printf("%d ",a[queue_min[head_min]]);
for(int i=2;i<=n-k+1;i++){
int x=i+k-1;
while(queue_min[head_min]<i&&head_min<=rear_min)head_min++;
while(a[x]<a[queue_min[rear_min]]&&head_min<=rear_min)rear_min--;
rear_min++;
queue_min[rear_min]=x;
printf("%d ",a[queue_min[head_min]]);
}
printf("\n");
printf("%d ",a[queue_max[head_max]]);
for(int i=2;i<=n-k+1;i++){
int x=i+k-1;
while(queue_max[head_max]<i&&head_max<=rear_max)head_max++;
while(a[x]>a[queue_max[rear_max]]&&head_max<=rear_max)rear_max--;
rear_max++;
queue_max[rear_max]=x;
printf("%d ",a[queue_max[head_max]]);
}
return 0;
}