Cod sursa(job #254050)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 6 februarie 2009 17:13:54
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
#include<string.h>

#define N 500010

char ch[500001<<3];
int dq[N], a[N], n, k;

int main(){
int max = -1000000, s, d, i, sf;

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n", &n, &k);
    gets(ch);

    a[1]=atoi(strtok(ch," \n"));

        dq[1] = 1; s = 1; d = 1;

        if (k == 1) max = a[1], sf = 1;

    for (i = 2; i <= n; i++){
            a[i]=atoi(strtok(NULL," \n"));

            if (dq[s] <= i-k && s <= d) s++;

            for ( ; a[dq[d]] >= a[i] && s<=d; d--);

            dq[++d] = i;

            if (i >= k) if (a[dq[s]] > max)
                max = a[dq[s]], sf = i;
    }

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