Cod sursa(job #847769)

Utilizator bogdan93Grigorescu Bogdan bogdan93 Data 4 ianuarie 2013 14:38:48
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <cstdlib>

#define nmax 500000

int N , k;
int deque[nmax] , v[nmax] , p , u , max = -30001;

int maxim ( int  &a , int &b )
{
    if ( a >= b ) return a;
        else return b;
}

int main ()
{
    FILE *fin , *fout ;

    fin = fopen ( "secventa.in" , "rt" );
    fout = fopen ( "secventa.out" , "wt" );

    fscanf ( fin , "%d %d" , &N , &k );

    p = 1 , u = 0 ;
    int poz = 0 ;
    for ( int i = 1 ; i <= N  ; i++ )
    {
        fscanf ( fin , "%d" , v + i );

        while ( v[i] <= v[deque[u]] && p <= u ) u--;
        deque[++u] = i;

        if ( deque[u] - deque[p] == k ) p++;

        if ( i >= k && max < v[deque[p]] )
        {
            poz = i;
            max = v[deque[p]];
        }
    }
    printf ( "%d %d %d\n" , poz - k + 1 , poz , max );
    fprintf ( fout , "%d %d %d\n" , poz - k + 1 , poz , max );

    fclose ( fin );
    fclose ( fout );

    return 0;
}