Pagini recente » Cod sursa (job #2143855) | Cod sursa (job #2773875) | Cod sursa (job #2168435) | Cod sursa (job #2363475) | Cod sursa (job #120377)
Cod sursa(job #120377)
#include<stdio.h>
#define N 500001
int a[N],n,k,coada[N];
char s[N*7];
int caut(int st,int dr,int poz){
int p=st,u=dr,m;
while(p<u){
m=(p+u)>>1;
if(a[poz]<=a[coada[m]])
u=m;
else
p=m+1;
}
if(a[coada[p]]<a[poz])
return p+1;
return p;
}
int main(){
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d\n",&n,&k);
gets(s);
int semn=1,i=1,p,u,max,aa,bb;
for(char*p=s;*p;++p)
if(*p=='-')
semn=-1;
else
if(*p==' '){
semn=1;
++i;
}
else
a[i]=a[i]*10+semn*(*p-'0');
/*
for(i=1;i<=n;++i)
printf("%d ",a[i]);
printf("\n");
*/
p=u=0;
coada[u]=1;
for(i=2;i<=k;++i){
u=caut(p,u,i);
coada[u]=i;
}
max=a[coada[p]];
aa=1;
bb=k;
for(i=k+1;i<=n;++i){
u=caut(p,u,i);
coada[u]=i;
if(i-coada[p]>=k)
++p;
if(a[coada[p]]>max){
aa=i-k+1;
bb=i;
max=a[coada[p]];
}
}
printf("%d %d %d\n",aa,bb,max);
return 0;
}