Cod sursa(job #999975)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 21 septembrie 2013 19:28:53
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h>

#define maxn 500010

int N, K;
int A[maxn], Deque[maxn];
int Front, Back;
int max, left, right;

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

    int i;

    scanf("%d %d ", &N, &K);

    for (i = 1; i <= N; i++)
        scanf("%d ", &A[i]);

    Front = 1, Back = 0;

    for (i = 1; i <= N; i++)
    {
        while (Front <= Back && A[i] <= A[ Deque[Back] ]) Back--;

        Deque[++Back] = i;

        if (Deque[Front] == i-K) Front++;

        if (i >= K && A[Deque[Front]] > max ) {
            max = A[Deque[Front]];
            left = Deque[Front];
            right = Deque[Back];
        }
    }

    while ( A[--left] >= max ) ;
    while ( A[--right] >= max && right-left >= K ) ;


    printf("%d %d %d\n",left+1,right+1,max);

    return 0;
}