Pagini recente » Cod sursa (job #2482902) | Cod sursa (job #114994) | Cod sursa (job #677902) | Cod sursa (job #627847) | Cod sursa (job #1643782)
#include <cstdio>
using namespace std;
int v[500005],n,i,k,q[500005],st[500005],dr[500005],m,in,sf,max1;
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d %d",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
q[1]=1;
m=1;
for(i=2;i<=n;i++)
{
if(v[i]>v[q[m]])
{
m++;
q[m]=i;
st[i]=i-1;
}
else
{
while(v[q[m]]>=v[i])
m--;
m++;
st[i]=st[q[m]];
q[m]=i;
}
}
q[1]=n;
m=1;
dr[n]=n+1;
for(i=n-1;i>=1;i--)
{
if(v[i]>v[q[m]])
{
m++;
q[m]=i;
dr[i]=i+1;
}
else
{
if(v[q[m]]>=v[i])
{
while(v[q[m]]>=v[i]&&m>=1)
m--;
m++;
}
if(v[i]>v[q[m]])
dr[i]=q[m];
else
dr[i]=dr[q[m]];
q[m]=i;
}
}
for(i=1;i<=n;i++)
{
if(v[i]>max1&&dr[i]-st[i]-1>=k)
{
max1=v[i];
in=st[i]+1;
sf=dr[i]-1;
}
}
printf("%d %d %d ",in,sf,max1);
return 0;
}