Cod sursa(job #604952)

Utilizator CristibaluCristi B Cristibalu Data 26 iulie 2011 11:15:24
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct list
{
    short info;
    int poz;
} S[500003];

int n ,k;
char s[3000010];


int main()
{
    int x, max = -31000;
    int i, umax = 0;
    list *nod, *aux;
    char *xs;
    int prim, ultim;

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

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

    gets(s);
    gets(s);

    xs = strtok(s, " ");
    i = 1;

    ultim = 0;
    prim = 1;

    while(xs != NULL)
    {
        x = atoi(xs);

        while(ultim>=prim && S[ultim].info > x)
        {
            ultim --;
        }

        if(ultim>=prim && i - S[prim].poz >= k)
        {
            prim++;
        }

        ultim ++;
        S[ultim].info = x;
        S[ultim].poz = i;


        if(i>=k && max < S[prim].info)
        {
            max = S[prim].info;
            umax = S[ultim].poz - k + 1;
        }

        xs = strtok(NULL, " ");
        i++;

    }

    printf("%d %d %d", umax, umax + k -1, max);

    return 0;
}