Pagini recente » Cod sursa (job #2413517) | Cod sursa (job #244499) | Cod sursa (job #258542) | Cod sursa (job #1634077) | Cod sursa (job #110031)
Cod sursa(job #110031)
#include <stdio.h>
int d[500001],c[500001];
int cauta(int val,int p,int u)
/*{
int m;
while (p<u)
{
m=(p+u)/2;
if (x<=c[m])
u=m;
else
p=m+1;
}
if (c[p]>=x)
return p;
return p+1;
}*/
//int binary_search(int val)
{
int i, step, N=u-p+1;
for (step = 1; step < N; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < N && c[i + step +p] <= val)
i += step;
if (c[i+p]>=val)
return i+p;
return i+p+1;
}
int main()
{
FILE *in,*out;
int n,k,aux,a,b,p,u,min,i,t;
in=fopen("secventa.in","r");
out=fopen("secventa.out","w");
fscanf(in,"%d%d",&n,&k);
min=-31000;
a=0;
b=0;
p=1;
u=1;
fscanf(in,"%d",&aux);
c[1]=aux;
d[1]=1;
for (i=2;i<k;i++)
{
fscanf(in,"%d",&aux);
t=cauta(aux,p,u);
c[t]=aux;
d[t]=i;
u=t;
}
for (i=k;i<=n;i++)
{
fscanf(in,"%d",&aux);
if (i-d[p]==k)
p++;
t=cauta(aux,p,u);
c[t]=aux;
d[t]=i;
u=t;
if (min<c[p])
{
min=c[p];
a=i-k+1;
b=i;
}
}
fprintf(out,"%d %d %d\n",a,b,min);
fclose(in);
fclose(out);
}