Pagini recente » Cod sursa (job #1963832) | Cod sursa (job #51639) | Cod sursa (job #1637168) | Cod sursa (job #3150146) | Cod sursa (job #1728983)
#include <cstdio>
using namespace std;
int n,i,v[500005],k,stv[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]);
stv[1]=1;
m=1;
st[1]=1;
max1=-999999;
for(i=2;i<=n;i++)
{
if(v[i]>v[stv[m]])
{
m++;
stv[m]=i;
st[i]=i;
}
else
{
while(v[i]<=v[stv[m]]&&m>=1)
m--;
m++;
st[i]=st[stv[m]];
stv[m]=i;
}
}
stv[1]=n;
m=1;
dr[n]=n;
for(i=n-1;i>=1;i--)
{
if(v[i]>v[stv[m]])
{
m++;
stv[m]=i;
dr[i]=i;
}
else
{
if(v[stv[m]]>=v[i])
{
while(v[stv[m]]>=v[i]&&m>=1)
m--;
m++;
}
dr[i]=dr[stv[m]];
stv[m]=i;
}
}
for(i=1;i<=n;i++)
if(v[i]>max1&&dr[i]-st[i]+1>=k)
{
in=st[i];
sf=dr[i];
max1=v[i];
}
printf("%d %d %d",in,sf,max1);
}