Cod sursa(job #16449)

Utilizator vlad_DVlad Dumitriu vlad_D Data 13 februarie 2007 04:33:58
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>

using namespace std;
int N, K;
int i, j;
int RMQ[19][500001];
int v[500001];
int MINU(int a, int b) {
	int lg = b - a + 1;
	int i, j;
	for (i=19; i>=0; i--) if ((1<<i) <=lg ) break;
	int X = (1<<i);
	int ret = RMQ[i][a];
	if (RMQ[i][b-X+1] < ret) ret = RMQ[i][b-X+1];
	return ret;
	}
int main() {
	freopen("secventa.in", "r", stdin);
	freopen("secventa.out", "w", stdout);
	scanf("%d %d", &N, &K);
	for (i=1; i< N+1; i++) {
		int X;
		scanf("%d", &X);
		v[i] = X;
		RMQ[0][i] = X;
		}
	int X = 1, X2 = 1;
	for (i=1; ;i++) {
		X<<=1;
		if (X > N) break;
		for (j=1; j+X-1 <=N; j++) {
			RMQ[i][j] = RMQ[i-1][j];
			if (RMQ[i-1][j+X-X2] < RMQ[i][j]) RMQ[i][j] = RMQ[i-1][j+X-X2];
		}
		X2 = X;
		}
	int sol = -31111, st, dr;
	for (i=1; i<=N-K+1; i++) {
		//minu pe i, i + K -1
		int A = i, B = i+K-1;
		int m = MINU(A, B);
		if (m > sol) {sol = m; st = i, dr = i+K-1;}
		
	} 
	printf("%d %d %d\n", st, dr, sol);
	return 0;
}