Cod sursa(job #1524549)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 14 noiembrie 2015 11:19:37
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#include <stdlib.h>
int v[500001],s[500001];
inline int citire()
{
    char c;
    int nr=0,semn=1;
    c=getchar();
    if(c=='-')
    {
        c=getchar();
        semn=-semn;
    }
    while(c>='0' && c<='9')
    {
        nr=nr*10+(c-'0');
        c=getchar();
    }
    return nr*semn;
}
int main()
{
    int n,k,i,u,j,max,p,a,b;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    getchar();
    for(i=1; i<=n; i++)
        v[i]=citire();
    u=0;
    for(i=1; i<=k; i++)
    {
        for(j=u; j>0; j--)
            if(v[i]>=v[s[j]])
                break;
        s[++j]=i;
        u=j;
    }
    max=v[s[1]];
    a=1;
    b=k;
    p=1;
    while(i<=n)
    {
        while(s[p]<i-k+1 && p<=u)
            p++;
        for(j=u; j>p-1; j--)
            if(v[i]>=v[s[j]])
                break;
        s[++j]=i;
        u=j;
        i++;
        if(v[s[p]]>max)
        {
            max=v[s[p]];
            a=i-k;
            b=i-1;
        }
    }
    printf("%d %d %d",a,b,max);

    return 0;
}