Cod sursa(job #1524541)

Utilizator demetriad-dagpagDavid Demetriad demetriad-dagpag Data 14 noiembrie 2015 11:16:05
Problema Secventa Scor 80
Compilator c Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <stdlib.h>
int v[500001],s[500001];
int citire()
{
    char c;
    int nr;
    c=getchar();
    while(c>='0' && c<='9')
    {
        nr=nr*10+(c-'0');
        c=getchar();
    }
    return nr;
}
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++)
        scanf("%d",&v[i]);
    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;
}