Cod sursa(job #1364248)

Utilizator BLz0rDospra Cristian BLz0r Data 27 februarie 2015 16:11:46
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <cstdio>
#include <deque>
using namespace std;

#define Nmax 500002
#define inf 0x3f3f3f3f

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

deque < int > Q;
int v[Nmax];

int main(){
	int N, K, st, dr, min = -inf;
	
	fscanf ( f, "%d%d", &N, &K );
	
	for ( int i = 1; i <= N; ++i ){
		fscanf ( f, "%d", &v[i] );
		
		while ( !Q.empty() && v[Q.back()] >= v[i] )
			Q.pop_back();
		
		Q.push_back ( i );
		
		if ( i >= K && v[Q.front()] > min ){
			min = v[Q.front()];
			st = Q.front();
			dr = i;
		}
		
		if ( Q.front() == i - K + 1)
			Q.pop_front();
	}
	
	fprintf ( g, "%d %d %d", st, dr, min );
	
	return 0;
}