Cod sursa(job #547703)

Utilizator cristian9Cristian Zloteanu cristian9 Data 6 martie 2011 17:27:45
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<stdio.h>
int deque[500001], v[500001];

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

    int n, i, k, z=1, max=-10000, x;

    scanf("%d %d ", &n, &k);

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

    int front=1, back=0;

    for(i=1; i<=n; i++){
        while(front<=back && v[i]<=v[deque[back]])
            back--;
        deque[++back]=i;
        while(front<=back && i-k>=deque[front]){
            front++;
        }
        if(v[deque[front]]>max && i>=k){
            max=v[deque[front]];
            x=i;
        }
    }

    printf("%d %d %d\n", x-k+1, x, max);
    return 0;
}