Cod sursa(job #1223623)

Utilizator pentrusandaPentru Sanda pentrusanda Data 28 august 2014 14:28:24
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <cstdio>

using namespace std;

int n,k,a[500005],lista[500005][2],st,dr,inceput,sfirsit,baza;

char c;

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);

    scanf("%d %d\n",&n,&k);

    c=' ';
    int i=0,semn=1;
    while (c!=EOF && c!='\n')
    {
        if (c==' ') a[i]*=semn,semn=1,++i;
        else
        {
            if (c=='-') semn=-1; else { a[i]=a[i]*10+(int)(c-'0'); }
        }
        c=getchar();
    }
    a[n]*=semn;

    st=1; dr=1; lista[1][0]=40000; lista[1][1]=0;
    for (int i=1;i<=k;++i)
    {
        ++dr;
        while (dr>st && lista[dr-1][0]>a[i]) --dr;
        lista[dr][0]=a[i];
        lista[dr][1]=i;
    }

    baza=lista[st][0]; inceput=1; sfirsit=k;

    for (int i=k+1;i<=n;++i)
    {
        if (i-lista[st][1]==k) ++st;
        ++dr;
        while (dr>st && lista[dr-1][0]>a[i]) --dr;
        lista[dr][0]=a[i];
        lista[dr][1]=i;
        if (lista[st][0]>baza) { baza=lista[st][0]; inceput=i-k+1; sfirsit=i; }
    }

    printf("%d %d %d",inceput,sfirsit,baza);

    fclose(stdin);
    fclose(stdout);
    return 0;
}