Pagini recente » Cod sursa (job #1982960) | Cod sursa (job #2810152) | Cod sursa (job #738076) | Cod sursa (job #963713) | Cod sursa (job #331750)
Cod sursa(job #331750)
#include<stdio.h>
typedef struct val{
int val,poz;
}val;
typedef struct qstack{
int ni,nf;
val v[500001];
}qstack;
int n,k;
qstack s;
char sir[3000001];
void pop(int poz){
if(poz-s.v[s.ni].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 next_number(int *j){
int nr=0,minus=0;
if(sir[*j]=='-'){
minus=1;
(*j)++;
}
while(sir[*j]!=' '){
nr=nr*10+sir[*j]-'0';
(*j)++;
}
(*j)++;
if(!minus)
return nr;
return -nr;
}
int main(){
int i,x,poz,a,j=0;
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
scanf("%d%d\n",&n,&k);
fgets(sir,3000001,stdin);
sir[strlen(sir)-1]=' ';
a=next_number(&j);
s.v[s.ni=s.nf=1].val=a;
s.v[s.nf].poz=1;
for(i=2;i<=k;i++){
a=next_number(&j);
push(a,i);
}
int max=s.v[s.ni].val;
poz=k;
for(;i<=n;i++){
a=next_number(&j);
pop(i);
push(a,i);
if((x=s.v[s.ni].val)>max){
max=x;
poz=i;
}
}
printf("%d %d %d",poz-k+1,poz,max);
return 0;
}