Cod sursa(job #931278)

Utilizator Master011Dragos Martac Master011 Data 28 martie 2013 09:28:39
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<cstdio>
using namespace std;
FILE *in,*out;
const int N = 500100;
int n,k,d[N],v[N],st=1,dr=1;

void citire(){
    fscanf(in,"%d%d",&n,&k);
    for(register int i=1;i<=n;i++)
        fscanf(in,"%d",&v[i]);
}

inline void stanga(int i){
    if(i-d[st]==k)
        st++;
}

void dreapta (int a){
    while(st<=dr    &&  v[d[dr]]>=a)
        dr--;
}

int main(){
    in=fopen("secventa.in","r");
    out=fopen("secventa.out","w");

    citire();

    d[1]=1;
    int inc,sf,max=0;
    for(register int i=2; i<=n; i++){
        stanga(i);
        dreapta(v[i]);
        d[++dr]=i;
        if(v[d[st]]>max){
            inc=i-k+1;
            sf=i;
            max=v[d[st]];
        }
    }

    fprintf(out,"%d %d %d",inc,sf,max);
    fclose(in);
    fclose(out);
    return 0;
}