Cod sursa(job #1364260)

Utilizator BLz0rDospra Cristian BLz0r Data 27 februarie 2015 16:19:14
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 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];
char s[Nmax*7];

int main(){
	int N, K, t = 1, st, dr, min = -inf;
	bool minus = 0;
	
	fscanf ( f, "%d%d%*c", &N, &K );
	
	fgets ( s, 7 * Nmax, f );
 
    for ( int i = 0; s[i]; ++i ) {
        if ( s[i] == ' ' || s[i] == '\n' ){
			if ( minus )
				v[t]= -v[t];
			minus = 0;
			t++;
        }
        else
            if ( s[i] == '-' )
				minus = 1;
        else
            v[t] = v[t] * 10 + (s[i] - '0');
    }
	
	for ( int i = 1; i <= N; ++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 = i - K + 1;
			dr = i;
		}
		
		if ( Q.front() == i - K + 1)
			Q.pop_front();
	}
	
	fprintf ( g, "%d %d %d", st, dr, min );
	
	return 0;
}