Pagini recente » Cod sursa (job #2633001) | Cod sursa (job #3209858) | Cod sursa (job #1996432) | Cod sursa (job #1076429) | Cod sursa (job #1270434)
#include<stdio.h>
typedef struct deque
{
int n,p;
}deque;
deque d[500002];
int v[500002];
char sir[5000000];
int main()
{
FILE *f=freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int n,k,a,i,j,s=-2000000000,p1=1,p2=1,semn=0;
scanf("%d%d\n",&n,&k);
fgets(sir,5000000,f);
i=0;j=1;
while(sir[i]!='\n')
{
if(sir[i]==' ')
++i;
if(sir[i]=='-')
{
semn=1;
++i;
}
while(sir[i]>='0'&&sir[i]<='9')
{
v[j]=v[j]*10+sir[i]-'0';
++i;
}
if(semn)
{
v[j]=-v[j];
semn=0;
}
++j;
}
i=1;j=0;
d[0].n=-200000000;
for(a=1;a<k;++a)
{
while(d[j].n>=v[a]&&j>=i)
--j;
++j;
d[j].n=v[a];
d[j].p=a;
}
for(a=k;a<=n;++a)
{
while(d[i].p<=a-k&&i<=j)
++i;
while(d[j].n>=v[a]&&j>=i)
--j;
++j;
d[j].n=v[a];
d[j].p=a;
if(d[i].n>s)
{
p1=a-k+1;
s=d[i].n;
}
}
p2=p1+k-1;
printf("%d %d %d\n",p1,p2,s);
return 0;
}