Cod sursa(job #2227961)

Utilizator LIR16LazarIonutRadu LIR16 Data 2 august 2018 12:47:43
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <iostream>
#include <deque>
#include <climits>
#include <utility>
#include <fstream>

using namespace std;

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

int main()
{
    long long n, k, numar;
    long long inceput, sfarsit, baza_max = LONG_LONG_MIN;
    deque< pair<int,int> > d; // first = valoarea, second = pozitia

    in >> n >> k;
    for( int i=1 ; i<=k ; i++ )
    {
        in >> numar;
        while( d.size() && d.front().first >= numar )
            d.pop_front();
        d.push_front({numar,i});
    }

    for( int i=k+1 ; i<=n ; i++ )
    {
        if( d.back().first > baza_max )
        {
            baza_max = d.back().first;
            sfarsit = d.front().second;
            inceput = sfarsit - k + 1;
        }
        in >> numar;
        while( d.size() && d.front().first >= numar )
            d.pop_front();
        while( d.size() && d.front().second - d.back().second + 1 > k )
            d.pop_back();
        d.push_front({numar,i});
    }

    while( d.size() && d.front().second - d.back().second + 1 > k )
    {
        d.pop_back();
        if( d.back().first > baza_max )
        {
            baza_max = d.back().first;
            sfarsit = d.front().second;
            inceput = sfarsit - k + 1;
        }
    }

    out << inceput << " " << sfarsit << " " << baza_max;
    return 0;
}