Cod sursa(job #1895297)

Utilizator NoSwearFlorea Marian NoSwear Data 27 februarie 2017 21:23:06
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#define NMAX 100005
using namespace std;
ifstream cin("rmq.in");
ofstream cout("rmq.out");
int n, m, i, j, x, y, lungime, p;
int d[18][NMAX];
int putere(int lungime)
{
    int p = 1;
    while((1 << p) < lungime)
    {
        p++;
    }
    p--;
    return p;
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        cin >> d[0][i];
    }
    for(i = 1; (1 << i) <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            d[i][j] = min(d[i - 1][j],
            d[i - 1][j + (1 << (i - 1))]);
        }
    }
    while(m--)
    {
        cin >> x >> y;
        if(x > y)
        {
            swap(x, y);
        }
        lungime = y - x + 1;
        p = putere(lungime);
        cout << min(d[p][x],
        d[p][y - (1 << p) + 1]) << "\n";
    }
    return 0;
}