Cod sursa(job #3240542)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 16 august 2024 11:49:15
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "secventa";

std :: ifstream in (FILENAME + ".in");

std :: ofstream out (FILENAME + ".out");

const int NMAX = 5e5 + 5;

const int INF = 1e5;

int n;

int k;

int v[NMAX];

int maxi;

int ans;

std :: deque <int> dq;

int main()
{

    in >> n >> k;

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

    for(int i = 1; i <= n; i ++)
    {
        while(!dq.empty() && i - dq.back() >= k)
        {
            dq.pop_back();
        }

        while(!dq.empty() && v[dq.front()] >= v[i])
        {
            dq.pop_front();
        }

        dq.push_front(i);

        if(i >= k && v[dq.back()] > maxi)
        {
            maxi = v[dq.back()];

            ans = i;
        }
    }

    out << ans - k + 1 << " " << ans << " " << maxi;

    return 0;
}