Pagini recente » Cod sursa (job #1805213) | Cod sursa (job #653920) | Cod sursa (job #2250778) | Cod sursa (job #311658) | Cod sursa (job #3199677)
// 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;
}