Cod sursa(job #2472332)

Utilizator victorv88Veltan Victor victorv88 Data 12 octombrie 2019 11:34:23
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;

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

deque<int>deck;

int n,k, sir[500005], maxi, ind_start, ind_end;

int main() {
    ios_base::sync_with_stdio(false);
    f >> n >> k;
    f >>sir[1];
    int el;
    deck.push_back(1);
    for (int i=2; i<=k; ++i)
    {
        f >> sir[i];
        while (!deck.empty() && sir[deck.back()]>sir[i])
            deck.pop_back();
        deck.push_back(i);
    }
    maxi=sir[deck.front()];
    ind_start=1;
    ind_end=k;
    for (int i=k+1; i<=n; ++i)
    {
        f >> sir[i];
        if (i-deck.front()>=k)
            deck.pop_front();
        while (!deck.empty() && sir[deck.back()]>sir[i])
            deck.pop_back();
        deck.push_back(i);
        if (sir[deck.front()]>maxi)
        {
            maxi=sir[deck.front()];
            ind_start=i-k+1;
            ind_end=i;
        }
    }
    g << ind_start <<' '<< ind_end <<' '<<maxi;
    return 0;
}