Cod sursa(job #1668941)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 30 martie 2016 10:43:11
Problema Secventa Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

int v[5000001],n,k,i,deque[5000001],p,u,Min,pi,pf;
char sir[350000],ch;
int len,temp,spy;

int gen_nr(){
    temp=0;
    spy=0;
    if(sir[i]=='-'){
        spy=1;
        i++;

    }

    while(sir[i]!=' ' && i<len){
        temp=temp*10+sir[i]-'0';
        i++;
    }
    if(spy==1){
        temp=-temp;
    }
    return temp;
}
int main(){
    int nr=1;

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);

    scanf("%d%d",&n,&k);
    scanf("%c",&ch);
    gets(sir);

    len=strlen(sir);

    for(i=0;i<len;i++){

        if((sir[i]>='0'&&sir[i]<='9') || sir[i]=='-' ){
            v[nr++]=gen_nr();
        }
    }

    p=1;
    u=1;
    Min=-1000000;
    for(i=1;i<=n;i++)
    {
        while(p<=u && v[i]<v[deque[u]]){
            u--;
        }
        deque[++u]=i;
        if(i-k==deque[p]){
            p++;
        }
        if(i>=k && v[deque[p]]>Min){
                Min=v[deque[p]];
                pi=i-k+1;
                pf=i;
        }
    }
    printf("%d %d %d",pi,pf,Min);
    return 0;
}