Cod sursa(job #3243714)

Utilizator gugalcromMuntoiu Vlad-Ioan gugalcrom Data 20 septembrie 2024 15:27:06
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

using namespace std;

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

    int N, K, i, j;

    fin >> N >> K;

    vector<int> a(N);
    deque<int> coada;
    int maxx=-32768, sf=-1;

    for(i=0; i<N; ++i) {
        fin >> a[i];
    }

    for(i=0; i<K; ++i) {
        while(!coada.empty() && a[coada.back()] >= a[i]) {
            coada.pop_back();
        }
        coada.push_back(i);
    }

    maxx = coada.front();
    sf = K;

    for(i=K; i<N; ++i) {
        while(!coada.empty() && a[coada.back()] >= a[i]) {
            //cout << a[coada.back()] << '*';
            coada.pop_back();
        }
        while(!coada.empty() && coada.front() < (i-K+1)) {
            //cout << a[coada.front()] << '!';
            coada.pop_front();
        }
        coada.push_back(i);
        if(a[coada.front()] > maxx) {
            maxx = a[coada.front()];
            sf = i;
        }
        //cout << coada.front();
        //cout << '\n';
    }

    fout << sf - K + 2 << ' ' << sf + 1 << ' ' << maxx << endl;

    return 0;
}