Pagini recente » Cod sursa (job #2035021) | Cod sursa (job #128660) | Cod sursa (job #1376893) | Cod sursa (job #962017) | Cod sursa (job #132747)
Cod sursa(job #132747)
// Problema 014.Secventa (infoarena). Varianta cu deque.
// Complexitate O(N)
#include <fstream.h>
int n, k, v[500000], deque[500000], qend, qbegin, min = -32000;
int main()
{
ifstream in("secventa.in");
ofstream out("secventa.out");
int i, pi, pf;
in>>n>>k;
for (i = 1; i <= n; i++) in>>v[i];
qbegin = 1;
for (i = 1; i < k; i++)
{
qend++;
while (qend > qbegin && v[i] <= v[deque[qend-1]]) qend--;
deque[qend] = i;
}
for (i = k; i <= n; i++)
{
qend++;
while (qend > qbegin && v[i] <= v[deque[qend-1]]) qend--;
deque[qend] = i;
if (deque[qbegin] <= i - k) qbegin++;
if (v[deque[qbegin]] > min)
{
min = v[deque[qbegin]];
pi = i - k + 1;
pf = i;
}
}
out<<pi<<" "<<pf<<" "<<min;
return 0;
}