Cod sursa(job #287543)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 24 martie 2009 22:33:17
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>

FILE *fin=fopen("secventa.in","r"),
    *fout=fopen("secventa.out","w");

int N,A[500005],dq[500005],li,lf,K;

int main(){
    fscanf(fin,"%d %d",&N,&K);
    for(int i=1;i<=N;i++)
        fscanf(fin,"%d",&A[i]);

    int pozi,pozf,min;
    li=1,lf=0;
    for(int i=1;i<=K;i++){
        while( lf>=li && A[i]<A[dq[li]] )
            --lf;
        dq[++lf]=i;
    }

    pozi=1,pozf=K,min=A[dq[1]];

    for(int i=K+1;i<=N;i++){

        while( lf>=li && A[i]<A[dq[lf]])
            --lf;
        dq[++lf]=i;

        if(li+1<=lf && A[dq[li+1]]>A[dq[li]] && i-dq[li]>=K)
            pozi=dq[li++]+1,pozf=i,min=A[dq[li]];
    }

    fprintf(fout,"%d %d %d\n",pozi,pozf,min);
    fclose(fin);
    fclose(fout);
    return 0;
}