Pagini recente » Cod sursa (job #3239870) | Cod sursa (job #1498800) | Cod sursa (job #410726) | Cod sursa (job #1492628) | Cod sursa (job #2439528)
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
ifstream in("rmq.in");
ofstream out("rmq.out");
const int dim = 100005;
int n,m,a[dim],rmq[20][dim];
int main()
{
in >> n >> m;
for (int i=1; i<=n; i++)
{
in >> a[i];
rmq[0][i] = a[i];
}
for (int j=1; (1<<j) <= n; j++)
{
for (int i=1; i + (1<<j) - 1 <=n; i++)
{
rmq[j][i] = min(rmq[j-1][i] , rmq[j-1][ i + (1<<(j-1))]);
}
}
int q,x,y,dif,log2;
while (m)
{
m--;
in >> x >> y;
dif = y-x+1;
log2 = (int)log(dif);
out << min(rmq[log2][x] , rmq[log2][y - (1<<log2) + 1]) << "\n";
}
return 0;
}