Cod sursa(job #2676399)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 24 noiembrie 2020 10:55:21
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <deque>

using namespace std;

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

const int NMAX = 500005;

int v[NMAX];

deque <int> dq;

int main()
{
    int n,k,i,maxim = -1,st,dr;
    fin>>n>>k;
    for(i = 1;i <= n;i++)
        fin>>v[i];
    for(i = 1;i < k;i++)
    {
        while(!dq.empty() && dq.front() > v[i])
            dq.pop_front();
        dq.push_front(v[i]);
    }
    for(;i <= n;i++)
    {
        while(!dq.empty() && dq.back() < i - k + 1)
            dq.pop_back();
        while(!dq.empty() && v[dq.front()] > v[i])
            dq.pop_front();
        dq.push_front(i);
        if(v[dq.back()] > maxim)
        {
            maxim = v[dq.back()];
            st = i - k + 1;
            dr = i;
        }
    }
    fout<<st<<" "<<dr<<" "<<maxim;
    return 0;
}