Cod sursa(job #772476)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 29 iulie 2012 21:31:49
Problema Range minimum query Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<fstream>
using namespace std;
ifstream fin("rmq.in"); ofstream fout("rmq.out");
int n, m, rmq[100001][18], a[100001], Log[100001];

void preprocess_RMQ(){
	int i, j, lgt;
	//process intervals of lenght 1
	for (i = 0; i < n; i++) rmq[i][0] = i;
	//process bigger intervals
	for (j = 1, lgt = 2; lgt < n; lgt = 1 << ++j)
		for (i = 0; i + lgt <= n; i++)
			if (a[rmq[i][j - 1]] > a[rmq[i + lgt / 2][j - 1]]) 
				rmq[i][j] = rmq[i + lgt / 2][j - 1];
			else 
				rmq[i][j] = rmq[i][j - 1];
}

int Minim(int x, int y){
	int left_min = a[rmq[x][Log[y - x]]];
	int right_min = a[rmq[y - (1 << Log[y - x]) + 1][Log[y - x]]];
	return left_min < right_min ? left_min : right_min;
}

int main(){
	int i, j, x, y, p;
	fin >> n >> m;
	for (i = 0; i < n; i++) fin >> a[i];
	for (i = 0, p = 1; p <= n; p = 1 << ++i)
		for (j = p; j < p * 2; j++)
			Log[j] = i;
		
	preprocess_RMQ();
	
	for (i = 0; i < m; i++)
		fin >> x >> y, fout << Minim(x - 1, y - 1) << "\n";
}