Pagini recente » Cod sursa (job #537010) | Cod sursa (job #1319035) | Cod sursa (job #2417359) | Cod sursa (job #1253938) | Cod sursa (job #258167)
Cod sursa(job #258167)
#include<stdio.h>
#define N 500020
int n,k,max,u,p,a,b;
int v[N],deq[N];
char s[N];
void citire()
{
scanf("%d%d\n",&n,&k);
fgets(s,N,stdin);
int i,nr=0,semn=1,x=0;
for(i=0;s[i];++i)
{
if(s[i]== ' ')
{
v[++nr]=semn*x;
x=0;
semn=1;
}
if(s[i]=='-')
semn=-1;
if(s[i]>='0' && s[i]<='9')
x=x*10+(s[i]-'0');
}
if(x)
v[++nr]=semn*x;
}
void proba()
{
for(int i=1;i<=n;++i)
printf("%d ",v[i]);
printf("\n");
}
void dreapta(int i)
{
while(u!=p && v[deq[u-1]]>=v[i])
--u;
deq[u++]=i;
}
void stanga(int i)
{
if(i-deq[p]>=k)
++p;
}
void solve()
{
for(int i=k+1;i<=n;++i)
{
stanga(i);
dreapta(i);
if(v[deq[p]]>max)
{
max=v[deq[p]];
a=i-k+1;
b=i;
}
}
printf("%d %d %d",a,b,max);
}
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
citire();
//proba();
//deq[u++]=1;
for(int i=1;i<=k;++i)
dreapta(i);
max=v[deq[p]];
b=k;
a=1;
solve();
return 0;
}