Cod sursa(job #1039708)

Utilizator TheNechizFMI Razvan Birisan TheNechiz Data 23 noiembrie 2013 14:31:02
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
# include <fstream>
# define dim 1000003
using namespace std;

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

int n,k,v[dim];

// Deque
int Deque[dim];
int prim;
int ultim;
// -- //

// Secventa
int Start;
int Finish;
int Maxim;
// -- //

int i; // index

void Citire()
{
    fin >> n >> k;
    for( i = 1 ; i <= n ; ++i )
        fin >> v[i];
    fin.close();
}

void Rezolv()
{
    prim = 1;
    ultim = 0;
    for( i = 1 ; i <= n ; ++i )
    {
        while( prim <= ultim && v[i] < v[Deque[ultim]] ) --ultim;
        Deque[++ultim] = i;
        if( Deque[prim] == i-k ) ++prim;
        if( i >= k  && Maxim < v[Deque[prim]] )
        {
            Start = i-k+1;
            Finish = i;
            Maxim = v[Deque[prim]];
        }
    }
}

void Tipar()
{
    fout << Start << ' ' << Finish << ' ' << Maxim;
    fout.close();
}

int main()
{
    Citire();
    Rezolv();
    Tipar();
    return 0;
}