Cod sursa(job #1569416)

Utilizator IoanZioan zahiu IoanZ Data 15 ianuarie 2016 15:28:09
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <cstdlib>

int v[500005],vf[60005],st[500005];

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);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    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;
}