Cod sursa(job #2676422)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 24 noiembrie 2020 11:18:46
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <fstream>
#include <deque>


#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")

using namespace std;

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

const int NMAX = 500005;

int v[NMAX];

deque <int> dq;

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    int n,k,i,maxim = -300000,st,dr;
    fin>>n>>k;
    for(i = 1;i <= n;i++)
        fin>>v[i];
    for(i = 1;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(i >= k && v[dq.back()] > maxim)
        {
            maxim = v[dq.back()];
            st = i - k + 1;
            dr = i;
        }
    }
    fout<<st<<" "<<dr<<" "<<maxim<<"\n";
    fin.close();
    fout.close();
    return 0;
}