Cod sursa(job #2365552)

Utilizator petrea1551Petrea Calin petrea1551 Data 4 martie 2019 14:42:31
Problema Range minimum query Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <bits/stdc++.h>
using namespace std;

int a[100001], rmq[100001][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;
	while (q * 2 <= n) q *= 2, t++;
	for (int j = 1; j < t; 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 << endl;
	}
	return 0;
}