Cod sursa(job #2622853)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 1 iunie 2020 22:55:17
Problema Secventa Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <climits>

using namespace std;

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

const int NMAX = 5e5 + 5;

int N, A[NMAX], Lg;

int Stiva[NMAX], K;
int Left[NMAX], Right[NMAX];

int ans = INT_MIN, pos_L, pos_R;

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> Lg;

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

    return;
}

static inline void Precalculation ()
{
    for(int i = 1; i <= N; ++i)
    {
        while(K && A[i] < A[Stiva[K]])
        {
            Right[Stiva[K]] = i;

            --K;
        }

        Stiva[++K] = i;
    }

    for(int i = 1; i <= K; ++i)
        Right[Stiva[i]] = (N + 1);

    K = 0;

    for(int i = N; i >= 1; --i)
    {
        while(K && A[i] < A[Stiva[K]])
        {
            Left[Stiva[K]] = i;

            --K;
        }

        Stiva[++K] = i;
    }

    return;
}

static inline void Solve ()
{
    for(int i = 1; i <= N; ++i)
    {
        int l = Left[i] + 1, r = Right[i] - 1;
        int k = r - l + 1;

        if(k >= Lg)
        {
            r = l + Lg - 1;

            if(A[i] > ans)
            {
                ans = A[i];

                pos_L = l, pos_R = r;

                continue;
            }

            if(A[i] == ans)
            {
                if(pos_L < l || (pos_L == l && pos_R > r))
                    pos_L = l, pos_R = r;
            }
        }
    }

    g << pos_L << ' ' << pos_R << ' ' << ans << '\n';

    return;
}

int main()
{
    Read();

    Precalculation();

    Solve();

    return 0;
}