Pagini recente » Cod sursa (job #362285) | Monitorul de evaluare | Statistici Bogdan Florin (oni2019) | Cod sursa (job #603695) | Cod sursa (job #331196)
Cod sursa(job #331196)
#include<stdio.h>
typedef struct val{
int val,poz;
}val;
typedef struct qstack{
int ni,nf;
val v[500001];
}qstack;
int n,k,a[500001];
qstack s;
void pop(int poz){
if(s.v[s.ni].poz-poz==k)
s.ni++;
}
void push(int val, int poz){
while(val<=s.v[s.nf].val){
s.nf--;
if(s.nf<s.ni)
break;
}
s.nf++;
s.v[s.nf].val=val;
s.v[s.nf].poz=poz;
}
int main(){
int i,x,poz;
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
s.v[s.ni=s.nf=1].val=a[n];
s.v[s.nf].poz=n;
for(i=n-1;i>n-k;i--)
push(a[i],i);
int max=s.v[s.ni].val;
poz=n-k+1;
for(;i>=1;i--){
pop(i);
push(a[i],i);
if((x=s.v[s.ni].val)>=max){
max=x;
poz=i;
}
}
printf("%d %d %d",poz,poz+k-1,max);
return 0;
}