Cod sursa(job #1223614)

Utilizator pentrusandaPentru Sanda pentrusanda Data 28 august 2014 14:23:48
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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();
    }

    st=1; dr=1;
    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=dr;

    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;
}