Cod sursa(job #2767686)

Utilizator pielevladutPiele Vladut Stefan pielevladut Data 7 august 2021 13:48:30
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n, k;
int h[500500];
int dreapta[1010];
int stanga[1010];

void dr()
{
    stack<int> stiva;
    for(int i = 1; i <= n; i ++)
    {
        while(!stiva.empty() && h[i] < h[stiva.top()])
        {
            dreapta[stiva.top()] = i;
            stiva.pop();
        }
        stiva.push(i);
    }
    while(!stiva.empty())
    {
        dreapta[stiva.top()] = n + 1;
        stiva.pop();
    }
}

void st()
{
    stack<int> stiva;
    for(int i = n; i >= 1; i --)
    {
        while(!stiva.empty() && h[i] < h[stiva.top()])
        {
            stanga[stiva.top()] = i;
            stiva.pop();
        }
        stiva.push(i);
    }
    while(!stiva.empty())
    {
        stanga[stiva.top()] = 0;
        stiva.pop();
    }
}

int main()
{
    fin >> n >> k;
    for(int i = 1; i <= n; i ++)
    {
        fin >> h[i];
    }
    st();
    dr();
    int minim = 0, st = 0, dr = 0;
    for(int i = 1; i <= n; i ++)
    {
        if(dreapta[i] - stanga[i] - 1 >= k && h[i] > minim)
        {
            minim = h[i];
            st = stanga[i];
            dr = dreapta[i];
        }
    }
    fout << st + 1 << ' ' << dr - 1 << ' ' << minim;
    return 0;
}