Cod sursa(job #1569451)

Utilizator IoanZioan zahiu IoanZ Data 15 ianuarie 2016 16:25:36
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <cstdio>
#include <cstdlib>

int v[500005],vf[60005],st[500005],i=0;

char s[3500005];

int nr()
{
    int nr=0,c=1;
    while (s[i]==' ' || s[i]=='\n')
           i++;
    if (s[i]=='-')
    {
        c=-1;
        i++;
    }
    while (s[i]>='0' && s[i]<='9')
    {
        nr=nr*10+(s[i]-'0')*c;
        i++;
    }
    return nr;
}

int main()
{
    int n,k,i,j,max,x;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d\n",&n,&k);
    gets(s);
    for(i=1;i<=n;i++)
        v[i]=nr();
    v[0]=-30001;
    j=0;
    for(i=1;i<=n;i++)
    {
        while (v[vf[j]]>=v[i])
               j--;
        j++;
        vf[j]=i;
        st[i]=i-vf[j-1]-1;
    }
    v[n+1]=-30001;
    j=0;
    vf[0]=n+1;
    max=0;
    for(i=n;i>=1;i--)
    {
        while (v[vf[j]]>=v[i])
               j--;
        j++;
        vf[j]=i;
        x=vf[j-1]-i-1;
        if (st[i]+x+1>=k)
            if (v[i]>v[max])
                max=i;
    }
    printf("%d %d %d",max-st[max],max-st[max]+k-1,v[max]);
    return 0;
}