MINK - Huyền thoại Lục Vân Tiên
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
main()
{
long T,n,k,a[17001],left[17001],right[17001],r[17002],l[17002],f[17001];
scanf("%ld",&T);
for(long i=1;i<=T;i++)
{
scanf("%ld %ld",&n,&k);
for(long j=1;j<=n;j++)
scanf("%ld",&a[j]);
long u=1;
r[1]=1;
while(r[u]!=n+1)
{
long t=r[u]+1;
if(a[t]<a[r[u]])
{
for(long j=u;j>=1;j--)
{
if(a[t]<a[r[j]])
{
right[r[j]]=t-1;
u--;
}
else
break;
}
u++;
r[u]=t;
}
else if(t==n)
{
for(long j=u;j>=1;j--)
right[r[j]]=n;
break;
}
else
{
u++;
r[u]=t;
}
}
right[n]=n;
u=1;
l[1]=n;
//printf("%ld %ld %ld %ld",right[4],right[3],right[2],right[1]);
while(l[u]!=0)
{
long t=l[u]-1;
if(a[t]<a[l[u]])
{
for(long j=u;j>=1;j--)
{
if(a[t]<a[l[j]])
{
left[l[j]]=t+1;
u--;
}
else
break;
}
u++;
l[u]=t;
}
else if(t==n)
{
for(long j=u;j>=1;j--)
left[l[j]]=n;
break;
}
else
{
u++;
l[u]=t;
}
}
left[1]=1;
//printf("%ld %ld %ld",left[4],left[3],left[2]);
for(long j=1;j<=n;j++)
{
if(left[j]<j-k+1)
left[j]=j-k+1;
if(right[j]>j+k-1)
right[j]=j+k-1;
for(long t=left[j];t<=right[j]-k+1;t++)
f[t]=a[j];
}
for(long j=1;j<=n-k+1;j++)
printf("%ld ",f[j]);
printf("\n");
}
//getch();
}