Pagini recente » Borderou de evaluare (job #1297042) | Cod sursa (job #1168148) | Cod sursa (job #2199822) | Cod sursa (job #2342481)
#include <iostream>
#include <fstream>
#define lim 100001
using namespace std;
ifstream f("rmq.in");
ofstream g("rmq.out");
int n, m, v[lim], rmq[lim][20], Lg[lim];
void preprocess()
{
for(int i = 2; i <= n; ++i)
Lg[i] = Lg[i>>1] + 1;
for(int i = 1; i <= n; ++i)
rmq[i][0] = i;
for(int j = 1; (1<<j) < n; ++j)
for(int i = 1; i+(1<<j)-1 <= n; ++i)
if(v[rmq[i][j-1]] < v[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];
}
int main()
{
f >> n >> m;
for(int i = 1; i <= n; ++i)
f >> v[i];
preprocess();
for(int i = 1; i <= m; ++i)
{
int x, y, lg, sol;
f >> x >> y;
lg = Lg[y-x+1];
if(v[rmq[x][lg]] < v[rmq[y-(1<<lg)+1][lg]])
sol = rmq[x][lg];
else
sol = rmq[y-(1<<lg)+1][lg];
g << v[sol] << "\n";
}
}