Cod sursa(job #1636225)

Utilizator bob123bobelus bob bob123 Data 7 martie 2016 00:07:00
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#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;
                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,++nr;
                    --sf;
                    nr=0;
                    for(j=in;j<=sf;++j)
                        s[++nr]=a[j];
                }
            }
    }
    for(i=1;i<=nr;++i)
        printf("%d ", s[i]);
    return 0;
}