Cod sursa(job #1334222)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 4 februarie 2015 02:19:47
Problema Range minimum query Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#define DIM 100010
using namespace std;

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

int n, m, i, j, k;
int d[25][DIM], p;
int v[DIM],  x, y;

int min(int a, int b){
    if(b == 0) return a;
    if(a <= b) return a;
    else       return b;
}

void SetUp(){
    fin >> n >> m;
    for(i = 1; i <= n; i ++)
        fin >> d[0][i];
    for(i = 2; i <= n; i ++)
        v[i] = 1 + v[i/2];
    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))]);
    return;
}

void Query(){
    for(i = 1; i <= m; i ++){
        fin >> x >> y;
        p = v[y-x+1];
        fout << min(d[p][x], d[p][y-(1<<p)+1]) << "\n";
    }

}

int main(){
    SetUp();
    Query();
    return 0;
}