Cod sursa(job #207076)

Utilizator mihaipoascaPoasca Mihai mihaipoasca Data 11 septembrie 2008 15:52:27
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 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=1;
    dq[lf]=1;


    for(int i=2;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){
                if(sol<a[dq[li]]){
                    sol=a[dq[li]];
                    pozi=dq[li];
                    pozf=dq[lf];
                }
            }
            else
                if(dq[lf]-dq[li]+1>K){
                    if(a[dq[li+1]]>sol){
                        sol=a[dq[li+1]];
                        pozi=dq[li]+1;
                        pozf=dq[lf];
                    }
                    ++li;
                }

    }

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

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


}