Cod sursa(job #2375659)

Utilizator SweetHumanAvram Gheorghe SweetHuman Data 8 martie 2019 11:17:33
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

using namespace std;
ifstream f1("secventa.in");
ofstream f2("secventa.out");

int n,k,indique,maximoIndico;
deque<int> indicusMaximus;
vector<int> numere;

int main() {
    f1>>n>>k;
    int x;
    for(int i=0;i<n;i++){
        f1>>x;
        numere.push_back(x);
    }
    indicusMaximus.push_back(0);
    for(int i=1;i<k;i++){
        while(!indicusMaximus.empty() && numere[indicusMaximus.back()]>numere[i])
            indicusMaximus.pop_back();
        indicusMaximus.push_back(i);
    }
    indique = k;
    maximoIndico = indicusMaximus.front();
    for(int i=k;i<n;i++){
        if(i-k==indicusMaximus.front())
            indicusMaximus.pop_front();
        while(!indicusMaximus.empty() && numere[indicusMaximus.back()]>numere[i])
            indicusMaximus.pop_back();
        indicusMaximus.push_back(i);
        if(numere[indicusMaximus.front()]>=numere[maximoIndico]){
            indique = i+1;
            maximoIndico = indicusMaximus.front();
        }
    }
    for(int i = indique-k;i<indique;i++){
        f2<<numere[i]<<" ";
    }
    f2<<numere[maximoIndico];
    return 0;
}