Cod sursa(job #2034902)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 8 octombrie 2017 16:32:48
Problema Range minimum query Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");

int n, m, d[20][100005];

int exp(int x)
{
    int s=0, xx=1;
    while(xx<=x)
    {
        xx<<=1;
        s++;
    }
    return s-1;
}

void constructie()
{
    int p=1, k=exp(n);
    for(int i=1; i<=k; i++)
    {
        for(int j=1; j<=n-i; j++)
            d[i][j]=min(d[i-1][j], d[i-1][j+p]);
        p*=2;
    }
}

int putere1(int q)
{
    int x=1;
    while(q)
    {
        x<<=1;
        q--;
    }
    return x;
}

int rmq(int x, int y)
{
    int k=exp(y-x);
    int p=putere1(k);
    return min(d[k][x], d[k][y-p+1]);
}

int main()
{
    int i, x, y;
    fin>>n>>m;
    for(i=1; i<=n; i++)
        fin>>d[0][i];
    constructie();
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        fout<<rmq(x,y)<<'\n';
    }
    return 0;
}