Cod sursa(job #2365578)

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

int a[100004], rmq[100004][40], 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 t = log2(n);
	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 = log2(y - x + 1);
		int minn = min(a[rmq[x][t]], a[rmq[y + 1 - (1 << t)][t]]);
		cout << minn << '\n';
	}
	return 0;
}