Pagini recente » Cod sursa (job #3132909) | Cod sursa (job #754419) | Cod sursa (job #273486) | Cod sursa (job #1038457) | Cod sursa (job #132739)
Cod sursa(job #132739)
// Problema 014.Secventa (infoarena). Varianta cu deque.
// Complexitate O(N)
#include <stdio.h>
int n, k, v[500000], deque[500000], qend, qbegin, min = -32000;
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int i, pi, pf;
scanf("%d %d", &n, &k);
for (i = 1; i <= n; i++) scanf("%d",v+i);
qbegin = 1;
for (i = 1; 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;
}
}
printf("%d %d %d\n", pi, pf, min);
return 0;
}