Pagini recente » Cod sursa (job #460166) | Cod sursa (job #129044) | Cod sursa (job #132525)
Cod sursa(job #132525)
//Problema 014.Secventa (Infoarena). Varianta cu heap.
//Complexitate O(N*logN)
#include <stdio.h>
#include <string.h>
int n, k, h[500000], p[500000], poz[500000], d, v[500000], nr;
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);
}
void citire()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%ld %ld",&n,&k);
long semn=0, aux, i;
char sir[2000024];
fgetc(stdin);
fgets(sir, 2000024,stdin);
aux=strlen(sir);
nr=1;
for (i=0; i<aux; i++)
{
if (sir[i]=='-') semn=1;
if (sir[i]>='0' && sir[i]<='9')
{
v[nr]=v[nr]*10+sir[i]-'0';
}
if (sir[i]==' ' && semn) v[nr]*=-1, semn=0;
if (sir[i]==' ') nr++;
}
}
int main()
{
citire();
int i, min = -32000, pi, pf;
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;
}