Pagini recente » Cod sursa (job #1163941) | Cod sursa (job #565246) | Cod sursa (job #2693218) | Cod sursa (job #1035471) | Cod sursa (job #196361)
Cod sursa(job #196361)
#include <stdio.h>
#define N 500100
#define min(a,b) a<b?a:b
int n,k;
int a[N],q[N],poz[N];
int max=-(1<<30),pi,pf;
char s[1<<22];
void parsare(){
int i,j,x;
scanf("%d%d\n",&n,&k);
fgets(s,1<<22, stdin);
for(j=0,i=1;i<=n;++j,++i){
if(s[j]=='-'){
for(x=0,j++;s[j]>='0'&&s[j]<='9';++j)
x=x*10+(s[j]-48);
a[i]=x*(-1);
}
else{
for(x=0;s[j]>='0'&&s[j]<='9';++j)
x=x*10+(s[j]-48);
a[i]=x;
}
}
}
int main(void){
freopen("secventa.in", "r", stdin);
freopen("secventa.out", "w", stdout);
parsare();
int i,inc=1,sf=1,baza;
q[1]=a[1];
poz[1]=1;
for(i=2;i<k;++i){
while(a[i]<=q[sf]&&sf>0)
sf--;
q[++sf]=a[i];
poz[sf]=i;
}
for(i=k;i<=n;++i){
while(i-poz[inc]>=k)
++inc;
baza=min(a[i],q[inc]);
if(baza>max){
max=baza;
pi=i-k+1;
pf=i;
}
while(a[i]<=q[sf]&&sf>0)
--sf;
q[++sf]=a[i];
poz[sf]=i;
if(inc>sf)
inc=sf;
}
printf("%d %d %d\n",pi,pf,max);
return 0;
}