Cod sursa(job #3031265)

Utilizator matei.tudoseMatei Tudose matei.tudose Data 19 martie 2023 12:56:33
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <deque>
using namespace std;

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

int N, K, sir[500001], baza_maxima = -30001, indice_start, indice_end;
deque<int> sirul_de_indici;

void stergere_val_mai_mici(int indice_el_nou)
{
    while (!sirul_de_indici.empty() && sir[sirul_de_indici.back()] >= sir[indice_el_nou])
        sirul_de_indici.pop_back();
}

void verificare_vechime_deque(int indice_el_nou)
{
    while (!sirul_de_indici.empty() && sirul_de_indici.front() <= indice_el_nou - K)
        sirul_de_indici.pop_front();
}

void rezolvare()
{
    sirul_de_indici.push_back(0);
    for (int i = 1; i < K; i++)
    {
        stergere_val_mai_mici(i);
        sirul_de_indici.push_back(i);
    }
    for (int i = K; i < N; i++)
    {
        stergere_val_mai_mici(i);
        verificare_vechime_deque(i);
        sirul_de_indici.push_back(i);
        if (baza_maxima < sir[sirul_de_indici.front()])
        {
            baza_maxima = sir[sirul_de_indici.front()];
            indice_start = sirul_de_indici.front();
            indice_end = sirul_de_indici.back();
        }
    }
}

int main()
{
    fin >> N >> K;
    for (int i = 0; i < N; i++)
        fin >> sir[i];
    rezolvare();
    fout << indice_start + 1 << " " << indice_end + 1 << " " << baza_maxima << "\n";
    return 0;
}