Cod sursa(job #51744)

Utilizator arenakadaffKadaff arenakadaff Data 16 aprilie 2007 19:11:08
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <stdio.h>


long int v[500001] , st[500001] ;

int main()
{
	FILE *in  , *out ;
	in = fopen("secventa.in" , "rt") ;
	out = fopen("secventa.out" , "wt") ;
	long int n , k , inc , sf , max , x , y , i;
	fscanf(in , "%ld %ld" , &n , &k) ;
	inc = 1 ;
	sf = 1 ;
	fscanf(in , "%ld" , &v[1]) ;
	st[1] = 1 ;
	max = 0 ;
	for(i = 2 ; i <= k - 1 ; k++)
	{
		fscanf(in , "%ld" , &v[i]) ;
		while(v[st[sf]] > v[i] && sf >= inc) sf -- ;
		sf++ ;
		st[sf] = i ;
	}
	for( ; i <= n ; i++)
	{
		fscanf(in , "%ld" , &v[i]) ;
		while(v[st[sf]] > v[i] && sf >= inc) sf -- ;
		sf++ ;
		st[sf] = i ;
		if(v[st[inc]] > max)
		{
			max = v[st[inc]] ;
			x = i - k + 1 ;
			y = i ;
		}
		if(st[inc] == i - k + 1) inc++ ;
	}
	if(k == 1)
	{
		x = 1 ;
		y = 1 ;
		for(i = 2 , max = v[1] ; i <= n ; i++) if(max < v[i])
		{
			max = v[i] ;
			x = i ;
			y = i ;
		}
		fprintf(out , "%ld %ld %ld" , x , y , max) ;
	}
	else fprintf(out , "%ld %ld %ld" , x , y , max) ;
	fclose(in) ;
	fclose(out) ;
	return 0 ;
}