Cod sursa(job #931305)

Utilizator Master011Dragos Martac Master011 Data 28 martie 2013 10:00:45
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include<cstdio>
#include<ctype.h>
using namespace std;
FILE *in,*out;
const int N = 500100;
int n,k,d[N],v[N],st=1,dr=1;
char s[4000001];

void citire(){
    fscanf(in,"%d%d\n",&n,&k);
    int next=0,semn;
    fgets(s,4000000,in);
    for(register int i=1;i<=n;i++)
    {
        if(s[next]=='-')
            semn=-1,next++;
        else semn=1;
        while(isdigit(s[next]))
            v[i]=v[i]*10+s[next++]-'0';
        next++;
        v[i]=v[i]*semn;
    }
}

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=-1000000;
    for(register int i=2; i<=n; i++){
        stanga(i);
        dreapta(v[i]);
        d[++dr]=i;
        if(v[d[st]]>max &&  i>=k){
            inc=i-k+1;
            sf=i;
            max=v[d[st]];
        }
    }

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