Cod sursa(job #1631528)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 5 martie 2016 16:48:49
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>
#define N 500010

int deq[N],v[N];
int n,k;
int head,tail;


void pop_fr(){
    head--;
}

void push_fr(int a){
    deq[head]=a;
    head++;
}
void pop_bck(){
    tail++;
}


int main(){
    int i,min=-3000000,imin;

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);


    scanf("%d%d",&n,&k);
    for(i=0;i<n;i++){
        scanf("%d",&v[i]);
        deq[i]=N-1;
    }

    head=-1;
    tail=0;

    for(i=0;i<n;i++){
        while( (head>=tail && head>=0 ) && ( v[i]<v[ deq[head] ]  || deq[head]==N-1 ) ){
            pop_fr();
        }
        head++;
        push_fr(i);

        if(deq[tail]<i-k+2){
            pop_bck();
        }

        if(i>=k-1){
            if(v[ deq[tail] ] >min){
                min=v[ deq[tail] ];
                imin=deq[tail];
            }
        }

    }

    for(i=imin;i<imin+k;i++){
        printf("%d ",v[i]);
    }


    return 0;
}