Cod sursa(job #999949)

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

#define maxn 5000010

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

int main()
{
    freopen("deque.in", "r", stdin);
    freopen("deque.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];
        }
    }

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

    return 0;
}