Cod sursa(job #2356688)

Utilizator MattCMatei Coroiu MattC Data 26 februarie 2019 20:53:54
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

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

int v[500005];

deque < int > dq;

int main()
{
    int n, k, maxim = 0, i, poz, st, dr, cnt;

    fin >> n >> k;

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

    for (i = 1; i <= n; ++i)
    {
        while (!dq.empty() && v[i] <= v[dq.back()])
        {
            dq.pop_back();
        }
        dq.push_back(i);
        if (dq.front() == i - k)
        {
            dq.pop_front();
        }
        if (i >= k)
        {
            if (v[dq.front()] > maxim)
                maxim = v[dq.front()], poz = dq.front();
        }
    }

    st = dr = poz;
    cnt = k;
    while (st > 1 && cnt && v[st - 1] >= maxim)
    {
        --st;
        --cnt;
    }
    while (dr < n && cnt && v[dr + 1] >= maxim)
    {
        --cnt;
        ++dr;
    }

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

    return 0;
}