Cod sursa(job #3199677)

Utilizator ifrim.claudiaClaudia Ifrim ifrim.claudia Data 2 februarie 2024 12:59:40
Problema Secventa Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.59 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 = 500005;

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

int n, k, v[MAX_LIMIT];

int main()
{
  fin >> n >> k;

  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;
    }
  }

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

  return 0;
}