Pagini recente » Cod sursa (job #1072416) | Cod sursa (job #1754004) | Cod sursa (job #1026222) | Cod sursa (job #2469050) | Cod sursa (job #196349)
Cod sursa(job #196349)
#include<stdio.h>
FILE *f,*g;
int a[500000],q[500000],baza;
long i,n,k,poz[500000],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; baza=a[1]; poz[1]=1;
for(i=2;i<k;i++)
{ while(a[i]<=q[sf]&&sf>0) sf--; sf++;
q[sf]=a[i];
poz[sf]=i;
}
baza=q[1]; pi=1; pf=sf;
for(i=k;i<=n;i++)
{ while(i-poz[inc]+1>k) inc++;
if(a[i]<q[inc]&&a[i]>baza) { baza=a[i]; pi=poz[inc]; pf=i; }
if(q[inc]<=a[i]&&q[inc]>baza) { baza=q[inc]; pi=poz[inc]; pf=i; }
while(a[i]<=q[sf]&&sf>=inc) sf--; if(inc>sf) sf=inc-1; sf++;
q[sf]=a[i];
poz[sf]=i;
}
fprintf(g,"%ld %ld %d",pi,pf,baza);
fclose(g);
return 0;
}