Pagini recente » Cod sursa (job #1910994) | Cod sursa (job #2377412) | Cod sursa (job #1836759) | Cod sursa (job #890291) | Cod sursa (job #120098)
Cod sursa(job #120098)
#include<stdio.h>
int n,k,a[500001],co[500001],min,minmax;
char sir[3600000];
int cauta(int p,int u,int x)
{
int m;
while(p<u){
m=(p+u)/2;
if(x<=a[co[m]])
u=m;
else
p=m+1;
}
if(a[co[p]]<x)
return p+1;
return p;
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int min=30001,max,p=0,u=0,aa,bb;
scanf("%d%d\n",&n,&k);
int r,t=1;
int i=1;
char ok;
int semn=1;
gets(sir);
for(char *pp=sir;*pp;++pp){
if(*pp=='-')
{
++pp;
semn=-1;
a[i]=-(*pp-'0');
}
else
if(*pp>='0'&&*pp<='9')
a[i]=a[i]*10+(*pp-'0')*semn;
else{
++i;
semn=1;
}
}
/*
for(int i=1; i<=n; i++)
printf("%d ",a[i]);
printf("\n");
*/
co[u++]=1;
for(i=2; i<=k; i++){
u=cauta(p,u-1,a[i]);
co[u++]=i;
if(a[co[p]]<min)
min=a[co[p]];
}
max=min;
aa=1;bb=k;
for(i=k+1; i<=n; i++)
{
if(co[p]+k<=i)
++p;
u=cauta(p,u-1,a[i]);
co[u++]=i;
min=a[co[p]];
if(min>max){
max=min;
aa=i-k+1;
bb=i;
}
}
printf("%d %d %d\n",aa,bb,max);
return 0;
}