Cod sursa(job #287574)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 24 martie 2009 22:57:59
Problema Secventa Scor 80
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[lf]] )
            --lf;
        dq[++lf]=i;
    }

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

    for(int i=K+1;i<=N;i++){
        if(i-dq[li]==K)
            ++li;
        while( lf>=li && A[i]<A[dq[lf]])
            --lf;
        dq[++lf]=i;

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

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