Cod sursa(job #373931)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 15 decembrie 2009 14:55:48
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<cstdio>
#include<cstring>
#include<stdlib.h>
int pozim,pozsm,max,s,d,n,k,dq[500001],v[500001];
char a[4000001];
inline void st(int i)
{
    if(i-dq[s]==k)
        ++s;
}
void dr(int i)
{
    while(s<=d && v[dq[d]]>=v[i])
        --d;
    dq[++d]=i;
}
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d\n",&n,&k);
    gets(a);
    v[1]=atoi(strtok(a," \n"));
    for(int i=2;i<=n;i++)
        v[i]=atoi(strtok(NULL," \n"));
    dq[1]=1;
    s=d=1;
    for(int i=2;i<=k;i++)
        dr(i);
    pozim=1;
    pozsm=k;
    max=v[dq[s]];
    for(int i=k+1;i<=n;i++)
    {
        st(i);
        dr(i);
        if(v[dq[s]]>max)
        {
            pozim=i-k+1;
            pozsm=i;
            max=v[dq[s]];
        }
    }
    printf("%d %d %d",pozim,pozsm,max);
    return 0;
}