Cod sursa(job #984222)

Utilizator manutrutaEmanuel Truta manutruta Data 13 august 2013 20:45:37
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
# include <iostream>
# include <fstream>
# include <deque>
using namespace std;

# define MAXN 500010

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

int n, k;
int a[MAXN];
deque<int> coada;

int main()
{
    int sol = -30010, pi, pf;
    f >> n >> k;
    for (int i = 1; i <= n; i++) {
        f >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        while (!coada.empty() && a[i] <= a[coada.back()]) {
            coada.pop_back();
        }

        coada.push_back(i);

        if (coada.front() == i - k) {
            coada.pop_front();
        }

        if (i >= k && a[coada.front()] > sol) {
            sol = a[coada.front()];
            pi = i - k + 1;
            pf = i;
        }
    }

    g << pi << ' ' << pf << ' ' << sol;

    return 0;
}