Cod sursa(job #3199673)

Utilizator ifrim.claudiaClaudia Ifrim ifrim.claudia Data 2 februarie 2024 12:51:41
Problema Secventa Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.01 kb
// https://www.infoarena.ro/problema/secventa

// Gigel are un sir de N numere intregi. Toata lumea stie ca o secventa este un subsir de numere
// care apar pe pozitii consecutive in sirul initial. Gigel a definit baza unei secvente ca fiind
// minimul valorilor elementelor din secventa respectiva.

// Cerinta
// Fiind dat un numar natural K, determinati pentru Gigel o secventa de lungime cel putin K cu baza maxima.

#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

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

const int MAX_LIMIT = 500000;
const int MIN = -30000;
const int MAX = 30000;

struct result
{
  int start;
  int bmin;
} res;

int n, k, v[MAX_LIMIT];

int main()
{
  fin >> n >> k;
  int bmax = MIN;
  int bmin = MAX;

  for (int i = 1; i <= n; i++)
  {
    fin >> v[i];
  }

  // Deque to store indices of potential minimum values
  deque<int> dq;

  // Initialize the deque for the first window of size k
  for (int i = 1; i <= k; i++)
  {
    while (!dq.empty() && v[i] <= v[dq.back()])
      dq.pop_back();
    dq.push_back(i);
  }

  res.start = 1;
  res.bmin = v[dq.front()];

  for (int i = k + 1; i <= n; i++)
  {
    // Remove indices outside the current window
    while (!dq.empty() && dq.front() < i - k + 1)
      dq.pop_front();

    // Remove indices with values greater than or equal to v[i]
    while (!dq.empty() && v[i] <= v[dq.back()])
      dq.pop_back();

    dq.push_back(i);

    // Update result if a new minimum is found
    if (v[dq.front()] > res.bmin)
    {
      res.bmin = v[dq.front()];
      res.start = i - k + 1;
    }
  }

  // for (int i = 2; i <= n - k + 1; i++)
  // {
  //   int x = i + k - 1;
  //   int bmin = MAX;
  //   while (x >= i)
  //   {
  //     if (v[x] < bmin)
  //     {
  //       bmin = v[x];
  //     }
  //     x--;
  //   }

  //   if (bmax < bmin)
  //   {
  //     bmax = bmin;
  //     res.start = i;
  //     res.bmin = bmax;
  //   }
  // }

  fout << res.start << " " << res.start + k - 1 << " " << res.bmin << endl;

  return 0;
}