Pagini recente » Cod sursa (job #3177525) | Cod sursa (job #2721624) | Cod sursa (job #5108) | Cod sursa (job #337219) | Cod sursa (job #1636227)
#include <cstdio>
using namespace std;
int sf,nr,j,Max,Front,Back,n,k,i,s[500001],a[500001],dq[500001];
int main()
{
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
scanf("%d%d", &n, &k);
Front=1;Back=0;
for(i=1;i<=n;++i)
scanf("%d", &a[i]);
for(i=1;i<=n;++i){
while(Front<=Back&&a[i]<=a[dq[Back]])
--Back;
dq[++Back]=i;
if(dq[Front]==i-k)
++Front;
if(a[dq[Front]]>Max&&i>=k)
{
Max=a[dq[Front]];
nr=1;
int in=dq[Front]-1;
while(a[dq[Front]]<=a[in]&&in>0)
--in,++nr;
++in;--nr;
if(nr==0)
nr=1,in=dq[Front];
if(nr>=k){
nr=0;
for(j=in;j<=dq[Front];++j)
s[++nr]=a[j];
}
else{
sf=dq[Front]+1;
while((nr<k&&sf<=n)&&a[sf]>=a[dq[Front]])
++sf,++nr;
--sf;
if(nr==k){nr=0;
for(j=in;j<=sf;++j)
s[++nr]=a[j];
}
}
}
}
for(i=1;i<=nr;++i)
printf("%d ", s[i]);
return 0;
}