Cod sursa(job #1048541)

Utilizator techLaurentiu Avasiloaie tech Data 6 decembrie 2013 00:16:30
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <deque>

using namespace std;

FILE * fin = fopen ( "secventa.in" , "r" ) ;
ofstream fout ( "secventa.out" ) ;

int vect[500001] , minim = -300001 , numar , negativ ;
long n , k , i , poz ;
char rand[5000000] ;

int main()
{
    fscanf ( fin , "%ld %ld \n" , &n , &k ) ;

    deque <int> d ;

    fgets( rand , 5000000 , fin ) ;

    numar = 0 ; negativ = 0 ; n = 0 ;

    for ( i = 1 ; rand[i] != 0 ; i ++ )
    {
        if ( rand[i] == '-' )
        {
            negativ = 1 ;
        }
        else if ( rand[i] >= '0' && rand[i] <= '9' )
        {
            numar = numar * 10 + ( rand[i] - '0' ) ;
        }
        else
        {
            if ( negativ )
            {
                vect[++n] = -1 * numar ;
            }
            else
            {
                vect[++n] = numar ;
            }

            negativ = 0 ;
            numar = 0 ;
        }
    }


    for ( i = 1 ; i <= n ; i ++ )
    {
        while ( d.empty() == 0 && vect[i] <= vect[d.back()] )
        {
            d.pop_back() ;
        }

        d.push_back(i) ;

        if ( d.front() == i - k )
        {
            d.pop_front() ;
        }

        if ( i >= k )
        {
            if ( vect[d.front()] > minim )
            {
                minim = vect[d.front()] ;
                poz = i ;
            }
        }
    }

    fout << poz - k + 1 << " " << poz << " " << minim ;

    return 0;
}