Cod sursa(job #1522256)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 11 noiembrie 2015 14:20:26
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <algorithm>
#include <deque>

using namespace std;

deque <int> dq;
int v[500010];

int main ()
{
    freopen ("secventa.in", "r", stdin);
    freopen ("secventa.out", "w", stdout);

    int n, k;
    scanf ("%d %d", &n, &k);

    int ma = -40000, poz;
    for (int i = 1; i <= n; ++i)
    {
        scanf ("%d", &v[i]);

        while (!dq.empty () && dq.front () <= i - k)
            dq.pop_front ();

        while (!dq.empty () && (v[dq.back ()] >= v[i] || dq.back () <= i - k))
            dq.pop_back ();

        dq.push_back (i);

        if (i >= k && v[dq.front ()] > ma) ma = v[dq.front ()], poz = i;
    }

    printf ("%d ", poz - k + 1);
    printf ("%d ", poz);
    printf ("%d\n", ma);

    return 0;
}