Cod sursa(job #2856053)

Utilizator vladburacBurac Vlad vladburac Data 23 februarie 2022 12:18:48
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
const int MAXN = 5e5;

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

stack <int> s;
int v[MAXN+1];
int st[MAXN+1], dr[MAXN+1];
int main() {
  int n, k, i, ind, bmax, stanga, dreapta;
  fin >> n >> k;
  for( i = 1; i <= n; i++ ) {
    fin >> v[i];
    while( !s.empty() && v[i] < v[s.top()] ) {
      dr[s.top()] = i;
      s.pop();
    }
    st[i] = s.top();
    s.push( i );
  }
  while( !s.empty() ) {
    ind = s.top();
    dr[s.top()] = n + 1;
    s.pop();
    if( !s.empty() )
      st[ind] = s.top();
  }
  bmax = -3e5;
  for( i = 1; i <= n; i++ ) {
    if( dr[i] - st[i] - 1 >= k ) {
      if( v[i] > bmax ) {
        bmax = v[i];
        stanga = st[i] + 1;
        dreapta = dr[i] - 1;
      }
    }
  }
  fout << stanga << " " << dreapta << " " << bmax;
  return 0;
}