Cod sursa(job #3243357)

Utilizator Mihai_999Diaconeasa Mihai Mihai_999 Data 17 septembrie 2024 19:17:04
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <deque>
#define nl '\n'

using namespace std;

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

const int NMAX = 5*1e5+5;

int n, k, v[NMAX], finish, maxi;
deque<int> dq;

int main()
{
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    for (int i = 1; i <= k; i++)
    {
        while (!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();
        dq.push_back(i);
    }
    maxi = v[dq.front()];
    finish = k;
    for (int i = k+1; i <= n; i++)
    {
        while (!dq.empty() && v[i] <= v[dq.back()])
            dq.pop_back();
        if (!dq.empty() && i-dq.front() >= k)
            dq.pop_front();
        dq.push_back(i);
        if (v[dq.front()] > maxi)
        {
            maxi = v[dq.front()];
            finish = i;
        }
    }
    fout << finish-k+1 << ' ' << finish << ' ' << maxi;
    return 0;
}