Cod sursa(job #1092172)

Utilizator george_stelianChichirim George george_stelian Data 26 ianuarie 2014 17:33:13
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <cstdio>
#include <cstring>

using namespace std;

int v[500010],deq[500010],i,n,k,st,dr,maxx,a,x,nr;
char s[5000100];

int main()
{
    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);
    scanf("%d%d\n",&n,&k);
    gets(s);
    a=1;
    x=0;
    for(i=0;s[i]!=0;i++)
    {
        if(s[i]==' ')
        {
            v[++nr]=a*x;
            a=1;
            x=0;
        }
        else
        {
            if(s[i]=='-') a=-1;
            else x=x*10+s[i]-'0';
        }
    }
    v[++nr]=a*x;
    st=1;dr=0;
    maxx=-300000;
    for(i=1;i<=n;i++)
    {
        while(st<=dr && v[i]<=v[deq[dr]]) dr--;
        deq[++dr]=i;
        if(deq[st]==i-k) st++;
        if(i>=k && v[deq[st]]>maxx){maxx=v[deq[st]];a=i;}
    }
    printf("%d %d %d",a-k+1,a,maxx);
    return 0;;
}