Cod sursa(job #772479)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 29 iulie 2012 21:46:44
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 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, lng, half;
	//process intervals of length 1
	for (i = 0; i < n; i++) rmq[i][0] = i;
	//process bigger intervals
	for (j = 1, lng = 2; lng < n; lng = 1 << ++j)
		for (i = 0, half = lng / 2; i + lng <= n; i++)
			rmq[i][j] = a[rmq[i][j - 1]] > a[rmq[i + half][j - 1]] ? rmq[i + half][j - 1] : rmq[i][j] = rmq[i][j - 1];
}

int Minim(int x, int y){
	int l_min = a[rmq[x][Log[y - x]]];
	int r_min = a[rmq[y - (1 << Log[y - x]) + 1][Log[y - x]]];
	return l_min < r_min ? l_min : r_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 <= n; j++)
			Log[j] = i;
		
	preprocess_RMQ();
	
	for (i = 0; i < m; i++)
		fin >> x >> y, fout << Minim(x - 1, y - 1) << "\n";
}