Cod sursa(job #368741)

Utilizator dinuddinu dan dinud Data 25 noiembrie 2009 18:45:55
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.53 kb
#include<stdio.h>
#define INF 1<<30
int d[500100],v[500100],n,k,i,bi,bf,p,u,max;

int main(){
	FILE*f=fopen("secventa.in","r");
	FILE*g=fopen("secventa.out","w");
	
	fscanf(f,"%d %d\n",&n,&k);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&v[i]);
	p=1;u=0;max= -INF;
	for(i=1;i<=n;i++){
		while(p<=u && v[i]<=v[d[u]])
			u--;
		d[++u]=i;
		if(d[p]==i-k)
			p++;
		if(i>=k)
			if(v[d[p]]>max){
				max=v[d[p]];
				bi=d[u]-k+1;
				bf=d[u];
			}
			
	}
	
	fprintf(g,"%d %d %d",bi,bf,max);
	
	fclose(f);fclose(g);
	return 0;
}