Cod sursa(job #2328245)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 25 ianuarie 2019 15:51:30
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

const int NMAX=5e5+5;

int N, K, A[NMAX];

deque <int> D;

inline void Read ()
{
    f.tie(NULL);

    f>>N>>K;

    for(int i=1; i<=N; ++i)
        f>>A[i];
}

inline void Solve ()
{
    int Max=INT_MIN, First=1, Last=K;

    D.push_back(1);

    for(int i=2; i<=N; ++i)
    {
        while(!D.empty() && A[i] < A[D.back()])
            D.pop_back();

        D.push_back(i);

        if(i - D.front() == K)
            D.pop_front();

        if(i >= K && A[D.front()] > Max) // Baza secventei curente este retinuta in elementul de pe pozitia D.front(), din sirul citit;
        {
            Max=A[D.front()];

            First=i-K+1;
            Last=i;
        }
    }

    g<<First<<' '<<Last<<' '<<Max<<'\n';
}

int main()
{
    Read();

    Solve();

    return 0;
}