Cod sursa(job #2807867)

Utilizator andrei81Ragman Andrei andrei81 Data 24 noiembrie 2021 12:05:06
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

int n, k, maxx, v[500005], poz;
deque<int> dq;

int main()
{
    ios_base::sync_with_stdio(false);
    fin >> n >> k;

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

    for ( int i = 1; i <= k; i++ )
    {
        while ( !dq.empty() && v[dq.back()] >= v[i] )
            dq.pop_back();
        dq.push_back(i);
    }

    maxx = v[dq.front()];
    poz = 1;

    for ( int i = k + 1; i <= n; i++ )
    {
        while ( !dq.empty() && dq.front() <= i - k )
            dq.pop_front();

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

        dq.push_back(i);
        // maxx = max(maxx, v[dq.front()]);
        if ( v[dq.front()] > maxx )
        {
            maxx = v[dq.front()];
            poz = i - k + 1;
        }
    }

    fout << poz << " " << poz + k - 1 << " " << maxx;
}