Cod sursa(job #79294)

Utilizator vladcoderVlad Ion vladcoder Data 21 august 2007 17:40:14
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#define MIN( a, b ) ( (a) < (b) ) ? a : b
#define MAX( a, b ) ( (a) > (b) ) ? a : b
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define NMAX 500050

int main()
{
	FILE * fin;
	FILE * fout;
	int A[NMAX], DEQ[NMAX];
    int N, K, i, j, first, last, left, right, min;
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%d %d\n", &N, &K );
	for( i = 0; i < N; i++ ) fscanf( fin, "%d", &A[i] );
	first = 0; last = -1;
	for( i = 0; i < K; i++ )
	{
		while ((last >= first ) && ( A[DEQ[last]] > A[i] ) ) last--; // insert in deque
		last++;
		DEQ[last] = i;
	}
	min = A[DEQ[first]]; right = K - 1;
	for( i = K; i < N; i++ )
	{
		while ( (last >= first ) && ( A[DEQ[last]] > A[i] )) last--; // insert in deque
		last++;
		DEQ[last] = i;
		while (( first <= last ) && ( i - DEQ[first] >= K )) first++; // stabilize deque
		if ( A[DEQ[first]] > min )
		{
			min = A[DEQ[first]];
			right = i;
			
		}
	}
	fprintf( fout, "%d %d %d\n", right - K + 2, right + 1, min );
	fclose( fin );
	fclose( fout );
	return 0;
}