Cod sursa(job #979722)

Utilizator stefan.friptuPetru Stefan Friptu stefan.friptu Data 2 august 2013 16:32:53
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>

#define NMAX 500001
#define inf 1000000
#define PMAX 330000

int v[NMAX],d[NMAX],n,k,maxim=-inf,pf;
int p[PMAX];
int i,st=0,sf=1,j;

using namespace std;

int main () {

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

    scanf("%ld%ld",&n,&k);

    for(i=1;i<=n;i++)
        scanf("%ld",&v[i]);

    for(i=0;i<NMAX;i++)
        d[i]=inf;
    sf=0;
    for(i=1;i<=k;i++)
    {
        while(sf>0 && d[sf]>v[i])
            --sf;
        d[++sf]=v[i];
        p[sf]=i;
    }
    maxim=d[1],pf=k,st=1;
    for(i=k+1;i<=n;i++)
    {
        if(p[st]<i-k+1)
            st++;
        while(sf>=st && d[sf]>v[i])
            sf--;
        d[++sf]=v[i];
        p[sf]=i;
        if(maxim<d[st])
                maxim=d[st],pf=i;
    }
    printf("%ld %ld %ld\n",pf-k+1,pf,maxim);
    return 0;
}