Cod sursa(job #2356791)

Utilizator MattCMatei Coroiu MattC Data 26 februarie 2019 21:43:55
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[500005];
int deq[500005];

int main()
{
    int n, k, maxim = INT_MIN, i, st, dr, Front = 1, Back = 0;

    fin >> n >> k;

    for (i = 1; i <= n; ++i)
    {
        fin >> v[i];
    }

    for (i = 1; i <= n; ++i)
    {
        while (Front <= Back && v[i] <= v[deq[Back]])
            --Back;
        deq[++Back] = i;
        if (deq[Front] == i - k)
            ++Front;
        if (i >= k)
        {
            if (v[deq[Front]] > maxim)
            {
                maxim = v[deq[Front]], st = i - k + 1, dr = i;
            }
        }
    }

    fout << st << ' ' << dr << ' ' << maxim << '\n';

    return 0;
}