Cod sursa(job #36463)

Utilizator amadaeusLucian Boca amadaeus Data 23 martie 2007 16:32:56
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <deque>
#include <cstdio>

using namespace std;

struct p {
	int index, val;
};

int main() {
	deque< p > d;
	p x;
	int best = -66666, poz, N, K;

	freopen( "secventa.in", "r", stdin );
	freopen( "secventa.out", "w", stdout );

	scanf( "%d%d", &N, &K );
	
	for( int i=1; i<=N; i++ ) {
		x.index = i;
		scanf( "%d", &x.val );

		while( !d.empty() ) {
			if( d.back().val >= x.val )
				d.pop_back();
			else
				break;
		}
		
		d.push_back( x );

		if( d.front().index <= i-K )
			d.pop_front();

		if( best < d.front().val && i >= K ) {
			poz = i;
			best = d.front().val;
		}
	}
	printf( "%d %d %d\n", poz-K+1, poz, best );
	return 0;
}