Cod sursa(job #289386)

Utilizator DraStiKDragos Oprica DraStiK Data 26 martie 2009 18:37:38
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#define DIM 500005
int a[DIM],b[DIM];
int n,k,nrt,in;
void read ()
{
    int i;
    scanf ("%d%d",&n,&k);
    for (i=1; i<=n; ++i)
        scanf ("%d",&a[i]);
}
void solve ()
{
    int st=1,dr=0,i;
    for (i=1; i<k; ++i)
    {
        while (st<=dr && a[i]<=a[b[dr]])
            --dr;
        b[++dr]=i;
    }
    for (i=k; i<=n; ++i)
    {
        while (st<=dr && a[i]<=a[b[dr]])
            --dr;
        b[++dr]=i;
        while (st<=dr && b[st]<i-k+1)
            ++st;
        if (a[b[st]]>nrt)
        {
            nrt=a[b[st]];
            in=i;
        }
    }
    printf ("%d %d %d",in-k+1,in,nrt);
}
int main ()
{
    freopen ("secventa.in","r",stdin);
    freopen ("secventa.out","w",stdout);
    read ();
    solve ();
    return 0;
}