Cod sursa(job #1523279)

Utilizator Theodor1000Cristea Theodor Stefan Theodor1000 Data 12 noiembrie 2015 16:05:58
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#include <cstring>

using namespace std;

deque <int> dq;
int v[500010];
char ss[5000010];

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

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

    gets (ss);
    int nn = strlen (ss);

    int xx = 1, x = 0, p = 0;
    for (int i = 0; i < nn; ++i)
        if (ss[i] == ' ')
        {
            v[++p] = x;
            x = 0;
            xx = 1;
            continue;
        }

        else if (ss[i] == '-') xx = -1;
        else x = x * 10 + xx * (ss[i] - 48);

    v[n] = x;

    int ma = -40000, poz;
    for (int i = 1; i <= n; ++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;
}