Pagini recente » Cod sursa (job #2592655) | Cod sursa (job #196455) | Cod sursa (job #1135706) | Cod sursa (job #2143320) | Cod sursa (job #196360)
Cod sursa(job #196360)
#include<stdio.h>
FILE *f,*g;
int a[500001],q[500001],baza;
long i,n,k,poz[500001],inc,sf,pi,pf;
int main()
{ f=fopen("secventa.in","r"); g=fopen("secventa.out","w");
fscanf(f,"%ld%ld",&n,&k);
for(i=1;i<=n;i++) fscanf(f,"%d",&a[i]);
q[1]=a[1]; inc=sf=1; poz[1]=1;
for(i=2;i<k;i++)
{ while(a[i]<=q[sf]&&sf>0) sf--;
q[++sf]=a[i];
poz[sf]=i;
}
for(i=k;i<=n;i++)
{ while(i-poz[inc]>=k) ++inc;
if(a[i]<q[inc]&&a[i]>baza) { baza=a[i]; pi=i-k+1; pf=i; }
if(q[inc]<=a[i]&&q[inc]>baza) { baza=q[inc]; pi=i-k+1; pf=i; }
while(a[i]<=q[sf]&&sf>0) --sf; q[++sf]=a[i]; poz[sf]=i;
if(inc>sf) inc=sf;
}
fprintf(g,"%ld %ld %d",pi,pf,baza);
fclose(g);
return 0;
}