Cod sursa(job #1473881)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 20 august 2015 13:48:30
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#define Max(a, b) (a) > (b)? (a):(b)
const char iname[] = "secventa.in";
const char oname[] = "secventa.out";
const int MAXN = 500005;
const int MINVAL = -30005;
const int MAXVAL =  30005;
int A[MAXN], Deque[MAXN], n, k, maxbase = MINVAL;

int main()
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n ; ++i){
        scanf("%d", A+i);
    }
    int first = 1, last = 0, st, fn;
    for(int i = 1; i <= n; ++i){
        while(first <= last && Deque[first] <= i-k) first++;
        while(last >= first && A[Deque[last]] >= A[i]) last --;
        Deque[++last] = i;
        if(i>=k && A[Deque[first]] > maxbase){
            maxbase = A[Deque[first]];
            st = i-k+1;
            fn = i;
        }

    }
    printf("%d %d %d", st, fn, maxbase);
    return 0;
}