Mai intai trebuie sa te autentifici.

Cod sursa(job #2676433)

Utilizator cyg_dragos10Ivan Dragos cyg_dragos10 Data 24 noiembrie 2020 11:33:30
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 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],n,k,i,maxim = -300000,st,dr;

deque <int> dq;

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(NULL);
    fout.tie(NULL);
    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;
}