Cod sursa(job #254037)

Utilizator runnaway90Oprescu Radu Constantin runnaway90 Data 6 februarie 2009 16:40:49
Problema Secventa Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.71 kb
#include<stdio.h>
#define N 500010

int dq[N], a[N], n, k;

int main(){
int max = 0, s, d, i, inc, sfars;

    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d", &n, &k);
    scanf("%d",&a[1]);

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

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

    for (i=2;i<=n;i++){
            scanf("%d", &a[i]);
            if (i-dq[s] >= k) s++;
            for ( ; a[dq[d]] > a[i] && s<=d; d--);
            dq[d++] = i;
            if (i>=k) max=(a[dq[s]] > max ? a[dq[s]] : max);
            inc = (max == a[dq[s]] ? dq[s] : inc );
            sfars = ( max == a[dq[s]] ? i : sfars);
    }

    printf("%d %d %d\n",inc, sfars, max);
    return 0;
}