Cod sursa(job #1399682)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 24 martie 2015 21:11:41
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<cmath>

using namespace std;

ifstream f("rmq.in");
ofstream g("rmq.out");

int a[20][100005],Log[100005];
int n,m;

void citire()
{
    int i;
    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>a[0][i];
}

void constructie()
{
    int i,j;
    for(i=1; (1<<i) <= n; ++i)
        for(j=1; j <= n - (1<<i) + 1; ++j)
            a[i][j]=min(a[i-1][j],a[i-1][j+ (1<<(i-1))]);

    for(i=2; i <= n; i++)
        Log[i] = Log[i/2] + 1;
}

int main()
{
    int i,ac,x,y,dist;

    citire();
    constructie();

    for(i=1;i<=m;i++){
        f>>x>>y;
        dist= y - x + 1;
        ac=Log[dist];
        g<<min(a[ac][x],a[ac][y - (1<<ac) + 1])<<"\n";
    }
    return 0;
}