Cod sursa(job #1048536)

Utilizator techLaurentiu Avasiloaie tech Data 5 decembrie 2013 23:58:27
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin ( "deque.in" ) ;
ofstream fout ( "deque.out" ) ;

int vect[500001] , minim = -300001 ;
long n , k , i , poz ;

int main()
{
    fin >> n >> k ;

    deque <int> d ;

    for ( i = 1 ; i <= n ; i ++ )
    {
        fin >> vect[i] ;
    }

    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;
}