Cod sursa(job #1184914)

Utilizator hrazvanHarsan Razvan hrazvan Data 14 mai 2014 16:41:50
Problema Secventa Scor 60
Compilator c Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#define K_MAX 500000
#define INF 2000000000
int deq[ K_MAX ], poz[ K_MAX ];

int main()
{
    FILE *in = fopen ( "secventa.in", "r" );
    int n, k;
    fscanf ( in, "%d%d", &n, &k );
    int i, st = 0, dr = 0, max = -INF, rezs, rezd, rez, x;
    for ( i = 0; i < n; i++ ){
        fscanf ( in, "%d", &x );
        while ( poz[ st ] + k <= i && st < dr )    st++;
        if ( dr > st ){
            while ( x < deq[ dr - 1 ] && dr > st ){
                dr--;
            }
        }
        deq[ dr ] = x;
        poz[ dr ] = i;
        dr++;
        if ( deq[ st ] > max && i >= k ){
            max = deq[ st ];
            rezs = i - k + 1;
            rezd = i;
            rez = deq[ st ];
        }
    }
    fclose ( in );
    FILE *out = fopen ( "secventa.out", "w" );
    fprintf ( out, "%d %d %d", rezs + 1, rezd + 1, rez );
    fclose ( out );
    return 0;
}