Cod sursa(job #2266589)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 22 octombrie 2018 19:50:49
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <deque>


using namespace std;

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

struct el{
    int indice, nr;
};

int n, k;
deque <el> deq;

int main() {

    ios_base::sync_with_stdio(false);
    in >> n >> k;

    el x;

    in >> x.nr;
    x.indice = 1;
    deq.push_back(x);

    for (int i = 2; i < k; i++) {
        in >> x.nr;
        x.indice = i;

        while (!deq.empty() && x.nr < deq.back().nr)
            deq.pop_back();
        deq.push_back(x);

    }
    el maxi;
    maxi.nr = -30005;
/*    deq.pop_front();*/

    for (int i = k; i <= n; i++) {
        in >> x.nr;
        x.indice = i;

        while (!deq.empty() && x.nr < deq.back().nr) {
            deq.pop_back();
        }
        deq.push_back(x);
        if (deq.front().nr > maxi.nr) {
            maxi.nr = deq.front().nr;
            maxi.indice = i;
        }

        if (deq.back().indice - deq.front().indice == k - 1)
            deq.pop_front();
    }
        out << maxi.indice - k + 1 << " " << maxi.indice << " " << maxi.nr;

        return 0;
    }