Cod sursa(job #1462812)

Utilizator om6gaLungu Adrian om6ga Data 19 iulie 2015 01:57:12
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <stdio.h>
#include <string.h>

#define nmax 500005
#define SIZE 3500005

int n, k, baza, ind;
int a[nmax], deque[nmax], i, j, aux, len;
int first = 1, last = 0;
char string[SIZE];
char *nr;

int main()
{
    FILE *in, *out;
    in  = fopen("secventa.in", "r");
    out = fopen("secventa.out", "w");
    
    fscanf(in, "%d %d\n", &n, &k);
    
    fgets(string, SIZE, in);
    
    i = 1;
    len = strlen(string);
    for (j = 0; j < len; j++)
    {
        aux = j;
        if (string[j] == ' ')
            continue;
        if (string[j] == '-')
            j++;
        while (string[j] >= '0' && string[j] <= '9')
            a[i] = a[i]*10 + string[j++] - '0';
        a[i++] *= (string[aux] == '-' ? -1 : 1);
    }
    
    /*for (i = 1; i <= n; i++)
        printf("%d ", a[i]);
    printf("\n");
    getchar();*/
    
    for (i = 1; i <= n; i++)
    {   
        while(first <= last && a[i] <= a[deque[last]])
            last--;
        deque[++last] = i;

        if (i - deque[first] == k)
            first++;

        if (i >= k)
        {
            if (baza < a[deque[first]])
            {
                baza = a[deque[first]];
                ind = deque[first];
            }
        }
    }
    
    while (ind-1>0 && a[ind-1] >= baza)
        ind--;
    fprintf(out, "%d  %d  %d\n", ind, ind + k-1, baza);
}