Cod sursa(job #207072)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 11 septembrie 2008 15:37:47
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<stdio.h>

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

int N,K,a[500005];
int dq[500000];
int sol=-40000000,li,lf,pozi,pozf;

int main(){
    fscanf(fin,"%d %d",&N,&K);

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

    li=1;lf=0;

    int solaux=-40005,poziaux,pozfaux;

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

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

        dq[++lf]=i;

        if(lf>li)
            if(dq[lf]-dq[li]+1==K){
                solaux=a[dq[li]];
                poziaux=dq[li];
                pozfaux=dq[lf];
            }
            else
                if(dq[lf]-dq[li]+1>K){
                    solaux=a[dq[li+1]];
                    poziaux=dq[li]+1;
                    pozfaux=dq[lf];
                    ++li;
                }
                else;


        if(solaux>sol){
            sol=solaux;
            pozi=poziaux;
            pozf=pozfaux;
        }
        else
            if(solaux==sol && pozi==poziaux &&pozfaux>pozf)
                pozf=pozfaux;



    }

    fprintf(fout,"%d %d %d\n",pozi,pozf,sol);

    fclose(fin);
    fclose(fout);
    return 0;


}