Cod sursa(job #2331380)

Utilizator netfreeAndrei Muntean netfree Data 29 ianuarie 2019 15:55:44
Problema Range minimum query Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("rmq.in");
ofstream fout("rmq.out");

const int N_MAX = 100000 + 5; 

int nr[N_MAX], rmq[32][N_MAX];

int n, m;

void init(){
	for(int i = 1; i<=n; ++i)
		rmq[0][i] = i; 

	for(int nivel = 1; (1<<nivel) <= n; ++nivel)
		for(int i = 1; i <= n - (1<<nivel) + 1; ++i){
			if(nr[ rmq[nivel-1][i] ] < nr[rmq[nivel-1][ i + (1<< (nivel-1) ) ]])
				rmq[nivel][i] = rmq[nivel-1][i];
			else
				rmq[nivel][i] =  rmq[nivel-1][ i + (1<< (nivel-1) ) ];
		}

}

int query(int lo, int hi){
	int nivel = log2(hi-lo+1);
	return min(nr[ rmq[nivel][lo] ], 
			   nr[ rmq[nivel][hi - (1<<nivel) + 1] ]
			   );
}

int main(){
	fin >> n >> m;
	for(int i = 1; i<=n; ++i)
		fin >> nr[i];
	
	init();

	while(m--){
		int lo, hi; 
		fin >> lo >> hi;
		if(lo > hi)
			swap(lo, hi);
		fout << query(lo,hi) << "\n";
	}

	return 0;
}

//Andrei Muntean, 2019