Cod sursa(job #52002)

Utilizator arenakadaffKadaff arenakadaff Data 17 aprilie 2007 16:31:13
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <stdlib.h>


long int v[5001] , st[5001] ;
char s[10] ;

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, j = 0 , nr ;
	fscanf(in , "%ld %ld\n" , &n , &k) ;
	inc = 1 ;
	sf = 1 ;
//	fscanf(in , "%ld" , &v[1]) ;
//	fgets(s , 10 , in) ;
	fscanf(in , "%s" , s) ;
	if(s[0] == '-') j = 1 ;
	else j = 0 ;
	for(nr = 0 ; s[j] ; j++) nr = nr * 10 + s[j] - '0' ;
	if(s[0] == '-') nr *= - 1 ;
	v[1] = nr ;
	st[1] = 1 ;
	max = -31000 ;
	for(i = 2 ; i <= k - 1 ; i++)
	{
//		fscanf(in , "%ld" , &v[i]) ;
//		fgets(s , 10 , in) ;
		fscanf(in , "%s" , s) ;
		if(s[0] == '-') j = 1 ;
		else j = 0 ;
		for(nr = 0 ; s[j] ; j++) nr = nr * 10 + s[j] - '0' ;
		if(s[0] == '-') nr *= - 1 ;
		v[i] = nr ;
		while(v[st[sf]] > v[i] && sf >= inc) sf -- ;
		st[++sf] = i ;
	}
	for( ; i <= n ; i++)
	{
//		fscanf(in , "%ld" , &v[i]) ;
//		fgets(s , 10 , in) ;
		fscanf(in , "%s" , s) ;
		if(s[0] == '-') j = 1 ;
		else j = 0 ;
		for(nr = 0 ; s[j] ; j++) nr = nr * 10 + s[j] - '0' ;
		if(s[0] == '-') nr *= - 1 ;
		v[i] = nr ;
		while(v[st[sf]] > v[i] && sf >= inc) 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 ;
}