Cod sursa(job #2447101)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 12 august 2019 10:04:51
Problema Secventa Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <iostream>
#include <cstdio>
#define NMAX 500010
#define MININT -30010
using namespace std;

int v[NMAX];
int st[NMAX];
int dr[NMAX];
int n, k;

int calcSt(int i)
{
  for (int j = i - 1; j > 0; j = st[j])
  {
    if (v[j] < v[i])
      return j;
  }
  return 0;
}

int calcDr(int i)
{
  for (int j = i + 1; j <= n; j = dr[j])
  {
    if (v[j] < v[i])
      return j;
  }
  return n + 1;
}

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

  scanf("%d", &n);
  scanf("%d", &k);

  for (int i = 1; i <= n; ++i)
    scanf("%d", &v[i]);

  for (int i = 1; i <= n; ++i)
    st[i] = calcSt(i);

  for (int i = n; i >= 1; --i)
    dr[i] = calcDr(i);

  int maxSupport = MININT;
  int startPos = -1;

  for(int i = 1; i <= n; ++i)
    if (v[i] > maxSupport && dr[i] - st[i] - 1 >= k)
    {
      maxSupport = v[i];
      startPos = st[i] + 1;
    }

  printf("%d %d %d", startPos, startPos + k - 1, maxSupport);

  return 0;
}