Pagini recente » Cod sursa (job #552797) | Cod sursa (job #698572) | Cod sursa (job #3270699) | Cod sursa (job #2552787) | Cod sursa (job #195507)
Cod sursa(job #195507)
#include<stdio.h>
int n,c,ka,min=30010;
int v[500010],a[500010];
char p[3500010];
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);
}
void citeste()
{
int i,semn=1,aux=0,k=0;
fgets(p,3500010,stdin);
for(i=0; p[i]!='\0'; i++)
{
if((p[i]<='9')&&(p[i]>='0'))
aux=aux*10+p[i]-'0';
else
if(p[i]=='-')
semn=-1;
else
{
a[++k]=aux*semn;
aux=0;
semn=1;
}
}
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d\n",&n,&ka);
int i,poz;
citeste();
//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;
}