Pagini recente » Cod sursa (job #2424266) | Cod sursa (job #392172) | Cod sursa (job #863901) | Cod sursa (job #1117275) | Cod sursa (job #253093)
Cod sursa(job #253093)
#include <cstdio>
#define N 500200
#define M 10000000
int n,v[N],coada[N],p,u,max=-30001,a,b,k;
void read(){
int i,semn,x;
char sir[M];
freopen("secventa.in","r",stdin);
scanf("%d%d\n",&n,&k);
fgets(sir,M,stdin);
for (i = 0, x = 0, n = 0, semn = 1; sir[i]; ++i)
{
if (sir[i] == ' ')
{
v[++n] = x * semn;
x = 0;
semn = 1;
}
if (sir[i] == '-')
semn = -1;
if (sir[i] >= '0'&& sir[i] <= '9')
x = x * 10 + (sir[i] - '0');
}
v[++n]=x*semn;
}
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();
}