Pagini recente » Cod sursa (job #3141570) | Cod sursa (job #2138843) | Cod sursa (job #1653008) | Cod sursa (job #206885) | Cod sursa (job #126871)
Cod sursa(job #126871)
//secventa implementata cu deque
#include<stdio.h>
#include<values.h>
FILE*fin=fopen("secventa.in","r");
FILE*fout=fopen("secventa.out","w");
int main()
{
long i,j,n,k,max,s,st,dr,v[500001],dec[500001],ind[500001];
fscanf(fin,"%ld%ld",&n,&k);
for(i=1;i<=n;i++)
fscanf(fin,"%ld",&v[i]);
st=dr=1;
dec[1]=MAXINT;
for(i=1;i<=n;i++)
if(v[i]<dec[1]){dec[1]=v[i];ind[1]=i;}
max=dec[1];s=k;
for(i=k+1;i<=n;i++)
{
if(ind[st]<i-k+1) st++;
j=dr;
while(j>=st&&dec[j]>v[i]) j--;
dr=j+1;
dec[dr]=v[i];
ind[dr]=i;
if(max<dec[st]){max=dec[st];s=i;}
}
fprintf(fout,"%ld%c%ld%c%ld",s-k+1,' ',s,' ',max);
fclose(fin);
fclose(fout);
return 0;
}