Cod sursa(job #979750)

Utilizator thewildnathNathan Wildenberg thewildnath Data 2 august 2013 17:46:37
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include<stdio.h>

typedef struct deque
{
    int n,p;
}deque;

deque d[500002];
int v[500002];

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,k,a,i,j,s=-2000000000,p1=1,p2=1;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;++i)
        scanf("%d",&v[i]);
    i=1;j=0;
    d[0].n=-200000000;

    for(a=1;a<k;++a)
    {
        while(d[j].n>=v[a]&&j>=i)
            --j;
        ++j;
        d[j].n=v[a];
        d[j].p=a;
    }
    for(a=k;a<=n;++a)
    {
        if(d[i].p==a-k)
            ++i;
        while(d[j].n>=v[a]&&j>=i)
            --j;
        ++j;
        d[j].n=v[a];
        d[j].p=a;
        if(d[i].n>s)
        {
            p1=d[i].p;
            s=d[i].n;
        }
    }
    p2=p1+k-1;
    if(p2>n)
    {
        p1-=(n-p2);
        p2=n;
    }
    printf("%d %d %d\n",p1,p2,s);
    return 0;
}