Pagini recente » Borderou de evaluare (job #1754379) | Borderou de evaluare (job #2261449) | Borderou de evaluare (job #2508874) | Borderou de evaluare (job #1278106) | Cod sursa (job #1751803)
#include <stdio.h>
using namespace std;
int v[500005];
int deq[500005];
char buff[1000005];
int bufflen=1,pozbuff;
int read()
{
int x=0;
while(buff[pozbuff]<'0'||buff[pozbuff]>'9')
{
pozbuff++;
if(bufflen==pozbuff) {pozbuff=0;bufflen=fread(buff,1,1000000,stdin);}
}
while(buff[pozbuff]>='0'&&buff[pozbuff]<='9')
{
x=x*10+buff[pozbuff]-'0';
pozbuff++;
if(bufflen==pozbuff) {pozbuff=0;bufflen=fread(buff,1,1000000,stdin);}
}
return x;
}
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;
}