Cod sursa(job #2365594)

Utilizator petrea1551Petrea Calin petrea1551 Data 4 martie 2019 15:02:26
Problema Range minimum query Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.7 kb
#include <bits/stdc++.h>
using namespace std;

int a[1<<20], rmq[1<<20][20], n, m;
 
int main()
{
	ifstream cin("rmq.in");
	ofstream cout("rmq.out");
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		rmq[i][0] = i;
	}
	int q = 1, t = 1;
	for (int j = 1; (1<<j) <= n; j++)
		for (int i = 1; i <= n; i++)
			{
				if (a[rmq[i][j - 1]] <= a[rmq[i + (1 << (j - 1))][j - 1]])
					rmq[i][j] = rmq[i][j - 1];
				else
					rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
			}
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		int t = floor(log2(y - x + 1));
		int minn = min(a[rmq[x][t]], a[rmq[y + 1 - (1 << t)][t]]);
		cout << minn << '\n';
	}
	return 0;
}