Pagini recente » Cod sursa (job #1884373) | Profil anamaria.visan | Cod sursa (job #1553572) | Cod sursa (job #1942004) | Cod sursa (job #245029)
Cod sursa(job #245029)
#include<stdio.h>
#include<string.h>
#define INF 1<<30
#define MAXN 500011
int semn,j,x,ok,N,max,pi,pf,v[MAXN],d[MAXN],n,k,i,p,u;
char c[MAXN*10];
int main(){
FILE *f=fopen("secventa.in","r");
fscanf(f,"%d %d\n",&n,&k);
fgets(c,MAXN*10 - 1 ,f);
N=strlen(c); semn=1; j=0;
for(i=0;i<N;i++){
x=0;ok=0;
if(c[i] == '-') semn = -1;
while(c[i]>='0' && c[i]<='9' && i<=N){
x=x*10+(c[i]-48);
ok=1;
i++;
}
x=semn*x;
if(ok) {j++,v[j]=x;semn=1;}
}
fclose(f);
p=1; u=1;
d[1]=1;
max=-INF;
for(i=2;i<=n;i++){
while( d[p] <= i - k) p++;
while(v[i] < v[d[u]] && p<=u)
u--;
u++;
d[u]=i;
if(i>=k){
if(v[d[p]] > max){
max=v[d[p]];
pi=i-k+1;
pf=i;
}
}
}
FILE *g=fopen("secventa.out","w");
fprintf(g,"%d %d %d",pi,pf,max);
fclose(g);
return 0;
}