Cod sursa(job #2676278)

Utilizator justin.stoicaJustin Stoica justin.stoica Data 23 noiembrie 2020 21:32:37
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <fstream>
#include <stack>
using namespace std;
stack <int> st;
const int NMAX = 500005;
int v[NMAX], L[NMAX], R[NMAX];
int main()
{
    ifstream cin("secventa.in");
    ofstream cout("secventa.out");
    int n, k, maxx = 0, sum, stanga = 0, dreapta = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        cin >> v[i];
    }
    v[0] = v[n + 1] = -1e8;
    st.push(0);
    for(int i = 1; i <= n; i ++)
    {
        while(!st.empty() && v[i] < v[st.top()])
        {
            st.pop();
        }
        L[i] = st.top();
        st.push(i);
    }
    while(!st.empty())
    {
        st.pop();
    }
    st.push(n + 1);
    for(int i = n; i >= 1; i --)
    {
        while(!st.empty() && v[i] < v[st.top()])
        {
            st.pop();
        }
        R[i] = st.top();
        st.push(i);
    }

    for(int i = 1; i <= n; i ++)
    {
        sum = R[i] - L[i] - 1;
        if(sum >= k)
        {
            if(v[i] > maxx)
            {
                maxx = v[i];
                stanga = L[i] + 1;
                dreapta = R[i] - 1;
            }
        }
    }
    cout << stanga << " " << dreapta << " " << maxx;
    return 0;
}