Cod sursa(job #2446579)

Utilizator claudiu.gatinaFMI Claudiu Gatina claudiu.gatina Data 9 august 2019 18:14:40
Problema Secventa Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <cstdio>

#define NRMIN -30001
#define NRMAX 30001
#define NMAX 500003
#define VMAX 60003
#define OFFSET 30000
using namespace std;

int v[NMAX];
int f[VMAX];

void clean(int start, int end)
{
  for (int i = start; i <= end; ++i)
    f[v[i]] = 0;
}

int findNextMin(int x)
{
  while (!f[x])
    ++x;
  return x - OFFSET;
}

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

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

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

  int minimum = NRMAX;
  int posLastMin = 0;
  for (int i = 1; i <= k; ++i)
  {
    if (v[i] < minimum)
    {
      minimum = v[i];
      posLastMin = i;
    }
  }

  int sol = minimum;
  int solPos = 1;
  int roi = posLastMin + 1;
  minimum = v[roi];
  for (int i = posLastMin + 1; i <= n; ++i)
  {
    if (v[i] <= sol)
    {
      clean(roi, i);
      roi = i + 1;
      minimum = v[i + 1];
      continue;
    }
    if (v[i] < minimum)
      minimum = v[i];
    ++f[v[i] + OFFSET];
    if (i - roi == k - 1)
    {
      sol = minimum;
      minimum = findNextMin(minimum + 1 + OFFSET);
      solPos = roi;
      ++roi;
    }
  }

  printf("%d %d %d", solPos, solPos + k - 1, sol);
  return 0;
}