Cod sursa(job #33720)

Utilizator sima_cotizoSima Cotizo sima_cotizo Data 19 martie 2007 18:58:43
Problema Secventa Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <cstdio>
#include <cmath>
#define FIN "secventa.in"
#define FOUT "secventa.out"
#define MAX 500500
#define LOG 20

inline long min(long x, long y) {
	return (x<y) ? x:y;
}

long V[LOG][MAX];
long A[MAX], N, K;
long i,shl;
long dr, st, bz;
long poz, act;

inline long f(long x, long y) { // baza secventei de la x la y
	long d = (long) (log(y-x)/log(2));
	return min(V[d][x],V[d][y-(1<<d)+1]);
}

int main() {
	freopen(FIN, "r", stdin);
	scanf("%ld %ld", &N, &K);
	for (i=1; i<=N; ++i)
		scanf("%ld", A+i);
	fclose(stdin);

	for (i=1; i<=N; ++i)
		V[0][i] = A[i];
	for (shl=1; (1<<shl) <= N; ++shl) 
		for (i=1; i<=N; ++i)
			if ( i+(1<<(shl-1))<=N )
				V[shl][i] = min(V[shl-1][i], V[shl-1][(1<<(shl-1))+i]);
			else
				V[shl][i] = V[shl-1][i];

   	st = 1; dr=K;
	bz = f(st,dr);
	poz = 1; act = bz;
	for (i=K+1; i<=N; ++i) {
		act = min(act, A[i]);
		if ( act<f(i-K+1,K) ) {
			poz = i-K+1;
			act = f(i-K+1,i);
		}
		if ( act>bz ) {
			bz = act;
			st = poz; dr = i;
		}
	}

	freopen(FOUT, "w", stdout);
	printf("%ld %ld %ld\n", st,dr,bz);
	fclose(stdout);
	return 0;
}