Pagini recente » Cod sursa (job #2261396) | Cod sursa (job #1359403) | Istoria paginii runda/cni | Cod sursa (job #2342980) | Cod sursa (job #132524)
Cod sursa(job #132524)
//Problema 014.Secventa (Infoarena). Varianta cu heap.
//Complexitate O(N*logN)
#include <stdio.h>
int n, k, h[500000], p[500000], poz[500000], d, v[500000];
void swap(int x, int y)
{
int z;
z = h[x]; h[x] = h[y]; h[y] = z;
z = p[x]; p[x] = p[y]; p[y] = z;
z = poz[p[x]]; poz[p[x]] = poz[p[y]]; poz[p[y]] = z;
}
void urc(int k)
{
if (h[k] < h[(k-1)/2])
{
swap(k,(k-1)/2);
urc((k-1)/2);
}
}
void cobor(int k)
{
int min, st, dr;
st = 2 * k + 1;
dr = 2 * k + 2;
if (st < d && h[st] < h[k]) min = st;
else min = k;
if (dr < d && h[dr] < h[min]) min = dr;
if (min != k)
{
swap(k,min);
cobor(min);
}
}
void adaug(int k)
{
h[d] = k;
urc(d);
d++;
}
void sterg(int k)
{
swap(k, d-1);
d--;
cobor(k);
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int i, pi, pf, min = -32000;
scanf("%d %d",&n,&k);
for (i = 1; i <= n; i++) scanf("%d",v+i);
for (i = 1; i < k; i++) {p[d] = i; poz[i] = d; adaug(v[i]);}
for (i = k; i <= n; i++)
{
p[d] = i; poz[i] = d;
adaug(v[i]);
if (min < h[0])
{
min = h[0];
pi = i - k + 1;
pf = i;
}
sterg(poz[i-k+1]);
}
printf("%d %d %d\n",pi,pf,min);
return 0;
}