Pagini recente » Cod sursa (job #1916553) | Cod sursa (job #2689440) | Cod sursa (job #2914021) | Cod sursa (job #441405) | Cod sursa (job #195506)
Cod sursa(job #195506)
#include<stdio.h>
int n,c,ka,min=30010;
int v[500010],a[500010];
inline int father(int x)
{
return x>>1;
}
inline int left_son(int x)
{
return x<<1;
}
inline int right_son(int x)
{
return (x<<1)+1;
}
void upheap(int k)
{
int key=v[k];
while((k>1)&&(a[key]<a[v[father(k)]]))
{
v[k]=v[father(k)];
k=father(k);
}
v[k]=key;
}
void downheap(int k)
{
int son,aux;
do
{
son=0;
if(left_son(k)<=c)
son=left_son(k);
if((right_son(k)<=c)&&(a[v[son]]>a[v[right_son(k)]]))
son=right_son(k);
if(a[v[son]]>=a[v[k]])
son=0;
if(son)
{
aux=v[son];
v[son]=v[k];
v[k]=aux;
k=son;
}
}while(son);
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d",&n,&ka);
int i,poz;
for(i=1; i<=n; i++)
scanf("%d",&a[i]);
/*for(c=1; c<=n; c++)
{
scanf("%d",&v[c]);
upheap(c);
}
for(i=1; i<=n; i++)
printf("%d ",v[i]);
printf("\n");*/
for(c=1; c<=ka; c++)
{
v[c]=c;
upheap(c);
}
min=v[1];
poz=1;
c--;
for(i=ka+1; i<=n; i++)
{
while(i-v[1]+1>ka)
{
v[1]=v[c];
c--;
downheap(1);
}
v[++c]=i;
upheap(c);
if(a[v[1]]>a[min]){
min=v[1];
poz=i-ka+1;
}
}
printf("%d %d %d\n",poz,poz+ka-1,a[min]);
return 0;
}