凌艺樽 • 13天前
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],k;
int q[N],h=-1,t=0;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n;++i)
{
while(h<=t && q[h]<=i-k)h++;
while(h<=t && a[q[t]]>=a[i])t--;
q[++t]=i;
if(i>=k)printf("%d ",a[q[h]]);
}
memset(q,0,sizeof(q));h=-1;t=0;
printf("\n");
for(int i=1;i<=n;++i)
{
while(h<=t && q[h]<=i-k)h++;
while(h<=t && a[q[t]]<=a[i])t--;
q[++t]=i;
if(i>=k)printf("%d ",a[q[h]]);
}
return 0;
}
评论: