Cod sursa(job #455198)

Utilizator alecmanAchim Ioan Alexandru alecman Data 13 mai 2010 10:29:15
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 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;
	
	int l;

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

	int x, y;
	int shift;
	int diff;

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

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

	fclose(fin);
	fclose(fout);

	return 0;
}