Cod sursa(job #968077)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 1 iulie 2013 19:41:56
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <stdio.h>
int st,dr,k,n,v[500001],d[500001];
void stanga(int i){
    if(i-d[st]==k){
        st++;
    }
}
void dreapta(int i){
    while((st<=dr)&&(v[i]<=v[d[dr]])){
        dr--;
    }
}
int main(){
    int i,max=-30001,outst,outdr;
    FILE *fin,*fout;
    fin=fopen("secventa.in","r");
    fout=fopen("secventa.out","w");
    fscanf(fin,"%d%d",&n,&k);
    for(i=1;i<=n;i++){
        fscanf(fin,"%d",&v[i]);
    }
    for(i=1;i<=n;i++){
        stanga(i);
        dreapta(i);
        dr++;
        d[dr]=i;
        if((i-d[st]+1>=k)&&(v[d[st]]>max)){
            max=v[d[st]];
            outst=d[st];
            outdr=i;
        }
    }
    fprintf(fout,"%d %d %d\n",outst,outdr,max);
    return 0;
}