Cod sursa(job #2622856)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 1 iunie 2020 22:59:48
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <iostream>
#include <cstdio>
#include <climits>

using namespace std;

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;

namespace InParser
{
static const int BSIZE = (1 << 16);

int pos = BSIZE - 1;
char buff[BSIZE];

static inline char Char ()
{
    ++pos;

    if(pos == BSIZE)
    {
        pos = 0;

        int n = fread(buff, 1, BSIZE, stdin);

        if(n != BSIZE)
            for(int i = n; i < BSIZE; ++i)
                buff[i] = 0;
    }

    return buff[pos];
}

static inline int Int ()
{
    int r = 0, sign = 1;

    for( ; ; )
    {
        char Ch = Char();

        if(Ch == '-')
        {
            sign = -1;

            break;
        }

        if(Ch >= '0' && Ch <= '9')
        {
            r = (int)(Ch - '0');

            break;
        }
    }

    for( ; ; )
    {
        char Ch = Char();

        if(Ch >= '0' && Ch <= '9')
            r = r * 10 + (int)(Ch - '0');
        else
            break;
    }

    return (r * sign);
}
};

static inline void Read ()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("secventa.in", "r", stdin);
    freopen("secventa.out", "w", stdout);

    N = InParser :: Int(), Lg = InParser :: Int();

    for(int i = 1; i <= N; ++i)
        A[i] = InParser :: Int();

    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)
                continue;

            if(pos_L < l || (pos_L == l && r < pos_R))
                pos_L = l, pos_R = r;
        }
    }

    printf("%d %d %d", pos_L, pos_R, ans);

    return;
}

int main()
{
    Read();

    Precalculation();

    Solve();

    return 0;
}