Cod sursa(job #1290592)

Utilizator hrazvanHarsan Razvan hrazvan Data 11 decembrie 2014 15:32:07
Problema Secventa Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#define K_MAX 500000
#define INF 2000000000
int v[K_MAX], poz[K_MAX];

int main()
{
    FILE *in = fopen("secventa.in", "r");
    int n, k, minus;
    char ch;
    fscanf ( in, "%d%d ", &n, &k );
    int i, st = 0, dr = 0, rezs, rezd, rez = -INF;
    for ( i = 0; i < n; i++ ){
        minus = 1;
        ch = fgetc(in);
        while(ch == ' ')
            ch = fgetc(in);
        while(ch != ' ' && ch != '\n' && ch != EOF){
            if(ch == '-')
                minus = -minus;
            else{
                v[i] *= 10;
                v[i] += ch - '0';
            }
            ch = fgetc(in);
        }
        v[i] *= minus;
        if(i - poz[st] + 1 > k)
            st++;
        while(dr > st && v[poz[dr - 1]] > v[i])
            dr--;
        poz[dr] = i;
        dr++;
        if(i >= k - 1 && rez < v[poz[st]]){
            rezs = i - k + 1;
            rezd = i;
            rez = v[poz[st]];
        }
    }
    fclose ( in );
    FILE *out = fopen ( "secventa.out", "w" );
    fprintf ( out, "%d %d %d", rezs + 1, rezd + 1, rez );
    fclose ( out );
    return 0;
}