Pagini recente » Cod sursa (job #2568008) | Cod sursa (job #2313848) | Cod sursa (job #2449635) | Cod sursa (job #2545792) | Cod sursa (job #210392)
Cod sursa(job #210392)
#include <cstdio>
#define N 500050
int n,v[N],coada[N],p,u,max=-30001,a,b,k;
void read(){
int i;
freopen("secventa.in","r",stdin);
scanf("%d%d",&n,&k);
for (i=1;i<=n;++i)
scanf("%d",&v[i]);
}
void elimin(int i){
while(p<u && coada[p]+k<=i)
++p;
}
int caut(int x){
int p2=p,u2=u,m;
while(p2!=u2){
m=(p2+u2)/2;
if (x<=v[coada[m]])
u2=m;
else
p2=m+1;
}
if (v[coada[p2]]<x)
++p2;
return p2;
}
void solve(){
int i,q;
coada[u++]=1;
for(i=2;i<=k;++i){
q=caut(v[i]);
u=q;
coada[u++]=i;
}
max=v[coada[0]];
a=1;
b=k;
for(i=k+1;i<=n;++i){
//elimin toate elem din coada care sunt prea indepartate de elm curent
elimin(i);
q=caut(v[i]);
u=q;
coada[u++]=i;
if(v[coada[p]]>max){
max=v[coada[p]];
a=i-k+1;
b=i;
}
}
}
void write(){
freopen("secventa.out","w",stdout);
printf("%d %d %d\n",a,b,max);
}
int main(){
read();
solve();
write();
}