Pagini recente » Cod sursa (job #3168070) | Cod sursa (job #3158407) | Cod sursa (job #1312127) | Cod sursa (job #3256273) | Cod sursa (job #1042707)
#include<iostream>
#include<cstdio>
using namespace std;
int d[18][100005], maxpow[100005];
void precalculez()
{
maxpow[1] = 0;
for(int i = 2; i <= 100005; i ++)
maxpow[i]=maxpow[i/2] + 1;
}
int main()
{
FILE *fin, *fout;
fin=fopen("rmq.in", "r");
fout=fopen("rmq.out", "w");
int i, n, m, x, y, lg, j, l;
fscanf(fin, "%d %d", &n, &m);
precalculez();
lg=maxpow[n];
for(i = 1; i <= n; i++)
fscanf(fin, "%d", &d[0][i]);
for(i = 1; i <= lg; i ++)
for(j = 1; j <= n; j++)
d[i][j]=min(d[i-1][j], d[i-1][j+(1 << (i-1))]);
for(i = 0; i < m; i++)
{
fscanf(fin, "%d %d", &x, &y);
l = y - x + 1;
fprintf(fout, "%d\n", min(d[maxpow[l]][x], d[maxpow[l]][1 + y - (1 << (maxpow[l]))]));
}
}