Cod sursa(job #455197)

Utilizator alecmanAchim Ioan Alexandru alecman Data 13 mai 2010 10:27:23
Problema Range minimum query Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define input "rmq.in"
#define output "rmq.out"
#define NMAX 100001
#define LMAX 20

FILE *fin = fopen(input, "r"), *fout = fopen(output, "w");

int N, M, x;
int V[ NMAX ];
int lg[ NMAX ];
int RMQ[ LMAX ][ NMAX ];

int main()
{
	fscanf(fin, "%d %d", &N, &M);

	for(int i = 1; i <= N; ++i)
	{
		fscanf(fin, "%d", &V[ i ]);
		RMQ[ 0 ][ i ] = V[ i ];
	}

	lg[ 1 ] = 0;
	for(int i = 2; i <= N; ++i)
		lg[ i ] = lg[ i/2 ] + 1;

	for(int i = 1; (1 << i) <= N; ++i)
		for(int j = 1; j <= N - (1 << i) + 1; ++j)
			RMQ[ i ][ j ] = min(RMQ[ i-1 ][ j ], RMQ[ i-1 ][ j+ (1<<(i-1)) ]);

	int l;
	int x, y;
	int shift;

	for(;M--;)
	{
		fscanf(fin, "%d %d", &x, &y);

		l = lg[ y - x + 1];
		shift = y-x+1 - (1<<l);
		fprintf(fout, "%d\n", min(RMQ[ l ][ x ], RMQ[ l ][ x+shift ]));
	}

	fclose(fin);
	fclose(fout);

	return 0;
}