Cod sursa(job #474674)

Utilizator vladcatrinaVlad Catrina vladcatrina Data 4 august 2010 17:00:24
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <stdio.h>

FILE*f = fopen("secventa.in","r");
FILE*g = fopen("secventa.out","w");

int n,k,front,back,i,max,b1,b2;
int a[500010],d[500010];

int main(){
	
	max=-30001;
	
	fscanf(f,"%d %d",&n,&k);
	for(i=1;i<=n;i++){
		fscanf(f,"%d",&a[i]);
	}
	
	front=1,back=0;
	//d[1]=1;
//	b2 = b1 = 1;
	
	for(i=1;i<=n;i++){
		
		while(front<=back && a[i]<=a[d[back]])
			back--;
		
		d[++back]=i;
			
		if(i>=k && a[d[front]]>max){
			max=a[d[front]];
			b1 = i-k+1;
			b2 = i;
			
		}
		if(d[front] <= i-k+1)
			front++;
	}
	
	fprintf(g,"%d %d %d",b1,b2,max);
	
	fclose(f), fclose(g);
	return 0;
}