Pagini recente » Borderou de evaluare (job #1417130) | Borderou de evaluare (job #2096143) | Monitorul de evaluare | Borderou de evaluare (job #2547123) | Cod sursa (job #1751806)
#include <stdio.h>
using namespace std;
int v[500005];
int deq[500005];
char buff[1000005];
int lung=1,pozbuff;
int read()
{
int x=0,sgn=1;
while((buff[pozbuff]<'0'||buff[pozbuff]>'9')&&buff[pozbuff]!='-')
{
if(++pozbuff==lung)
{
lung=fread(buff,1,1000000,stdin);
pozbuff=0;
}
}
if(buff[pozbuff]=='-'){sgn=-1;pozbuff++;}
if(pozbuff==lung)
{
lung=fread(buff,1,1000000,stdin);
pozbuff=0;
}
while((buff[pozbuff]>='0'&&buff[pozbuff]<='9')||buff[pozbuff]=='-')
{
x=x*10+buff[pozbuff]-'0';
if(++pozbuff==lung)
{
lung=fread(buff,1,1000000,stdin);
pozbuff=0;
}
}
return x*sgn;
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
int n,k,i,p,u,a,poz,len,m=-1000000,deltapoz,pozfin;
n=read();
k=read();
for(i=1;i<=n;i++)
v[i]=read();
p=1;u=0;
for(i=1;i<=k;i++)
{
a=v[i];
while(p<=u&&v[deq[u]]>a)
u--;
deq[++u]=i;
}
if(m<v[deq[p]])
{
m=v[deq[p]];
poz=deq[p]; // i sau deq[p]
}
for(i=k+1;i<=n;i++)
{
a=v[i];
while(p<=u&&v[deq[u]]>a)
u--;
deq[++u]=i;
if(i-deq[p]>=k) p++;
if(m<v[deq[p]])
{
m=v[deq[p]];
poz=deq[p]; // i sau deq[p]
}
}
for(i=poz-1;v[i]>m;i--);
deltapoz=poz-i;
if(k<deltapoz) pozfin=poz;
else pozfin=poz+k-deltapoz;
printf("%d %d %d",i+1,pozfin,m);
//printf("%d %d %d",poz-k+1,poz,m);
return 0;
}