Pagini recente » Cod sursa (job #1654393) | Cod sursa (job #3164713) | Cod sursa (job #2444182) | Cod sursa (job #269371) | Cod sursa (job #973057)
Cod sursa(job #973057)
#include<stdio.h>
#define Dim 500001
int q[Dim] ;
long ind[Dim] ;
int main()
{
int x, max ;
long poz, pr, ul, n, k, i, p, w, minus ;
freopen("secventa.in","r",stdin) ;
freopen("secventa.out","w",stdout) ;
scanf("%ld %ld",&n,&k) ;
// calculez minimul din primele k:
pr = 0 ; ul = -1 ;
scanf("%s", &sir);w=0;
for (i=1; i<=k; i++)
{
//scanf("%d",&x);
x=0;minus=0;
if(sir[w]=='-')
{
minus=1;
w++;
}
while(sir[w]>='0' && sir[w]<='9')
{
x=x*10+sir[w]-'0';
w++;
}
if(minus==1)
x=-x;
w++;
while ((pr<=ul)&&(q[ul] >= x)) ul-- ;
q[++ul] = x ;
ind[ul] = i ;
}
max = q[pr] ;
poz = 1 ;
p = 1;
// calculez restul:
for ( ; i<=n; i++)
{
//scanf("%d",&x) ;
x=0;minus=0;
if(sir[w]=='-')
{
minus=1;
w++;
}
while(sir[w]>='0' && sir[w]<='9')
{
x=x*10+sir[w]-'0';
w++;
}
if(minus==1)
x=-x;
w++;
while ((q[ul] >= x) && (pr<=ul)) ul-- ;
q[++ul] = x ;
ind[ul] = i ;
p++ ;
if (ind[pr] <= i-k) pr++ ;
if (max < q[pr]) { max = q[pr] ;poz = p; }
}
printf("%ld %ld %d\n",poz,poz+k-1,max) ;
return 0 ;
}