Pagini recente » Cod sursa (job #364868) | Cod sursa (job #581245) | Cod sursa (job #1596640) | Cod sursa (job #2296921) | Cod sursa (job #331421)
Cod sursa(job #331421)
#include<stdio.h>
#include<stdlib.h>
typedef struct qstack{
int ni,nf;
int val[500001];
int poz[500001];
}qstack;
/*typedef struct qstack{
int ni,nf;
int *val;
int *poz;
}qstack;*/
int n,k;
qstack s;
/*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 main(){
int i,x,poz,a;
/*freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);*/
FILE *f=fopen("secventa.in","r"),*g=fopen("secventa.out","w");
fscanf(f,"%d%d",&n,&k);
fscanf(f,"%d",&a);
s.val[s.ni=s.nf=1]=a;
s.poz[s.nf]=1;
for(i=2;i<=k;i++){
fscanf(f,"%d",&a);
//push(a,i);
while(a<s.val[s.nf]){
s.nf--;
if(s.nf<s.ni)
break;
}
s.nf++;
s.val[s.nf]=a;
s.poz[s.nf]=i;
}
int max=s.val[s.ni];
poz=k;
for(;i<=n;i++){
fscanf(f,"%d",&a);
//pop(i);
if(i-s.poz[s.ni]==k)
s.ni++;
//push(a,i);
while(a<s.val[s.nf]){
s.nf--;
if(s.nf<s.ni)
break;
}
s.nf++;
s.val[s.nf]=a;
s.poz[s.nf]=i;
if((x=s.val[s.ni])>max){
max=x;
poz=i;
}
}
fprintf(g,"%d %d %d",poz-k+1,poz,max);
return 0;
}