Pagini recente » Cod sursa (job #2267113) | Cod sursa (job #3267048) | Cod sursa (job #1046698) | Cod sursa (job #1945170) | Cod sursa (job #3199673)
// 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;
}