Pagini recente » Statistici iordache cezar (DormeoBoy) | Cod sursa (job #363544) | Cod sursa (job #1286057) | Cod sursa (job #1991452) | Cod sursa (job #131843)
Cod sursa(job #131843)
#include<stdio.h>
#include<string.h>
#define lim 3150000
struct cod{
int x,t;
};
cod coada[500100];
char sir[lim];
int ax[500100];
int main(){
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int n,k,i,p,u,mij,timp,inc,sf,max=-50000,aux,tfin;
scanf("%d%d\n",&n,&k);
inc=0;
sf=0;
timp=0;
fgets(sir,lim,stdin);
int l=strlen(sir),semn;
p=0;
for(i=0;i<=l;++i){
if(sir[i]==' ' || sir[i]=='\n'){
if(semn==1)
ax[p]=aux;
else
ax[p]=-aux;
semn=1;
aux=0;
++p;
}
if(sir[i]=='-')
semn=-1;
if('0'<=sir[i] && sir[i]<='9')
aux=aux*10+(sir[i]-'0');
}
coada[0].x=ax[0];
coada[0].t=0;
max=coada[0].x;
for(i=1;i<k;++i){
p=inc;
u=sf;
while(p!=u){
mij=(p+u)>>1;
if(coada[mij].x<ax[i])
p=mij+1;
else
u=mij;
}
if(coada[p].x<ax[i])
++p;
++timp;
coada[p].x=ax[i];
coada[p].t=timp;
sf=p;
if(coada[sf].x<max)
max=coada[sf].x;
}
tfin=0;
for(;i<n;++i){
if(coada[inc].t+k<=i)
++inc;
p=inc;
u=sf;
while(p!=u){
mij=(p+u)>>1;
if(coada[mij].x<ax[i])
p=mij+1;
else
u=mij;
}
if(coada[p].x<ax[i])
++p;
++timp;
coada[p].x=ax[i];
coada[p].t=timp;
sf=p;
if(coada[inc].x>max){
max=coada[inc].x;
if(tfin+k>=i)
++tfin;
else
tfin=i-k+1;
}
}
printf("%d %d %d\n",tfin+1,tfin+k,max);
fclose(stdin);
fclose(stdout);
return 0;
}