Cod sursa(job #2361369)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 2 martie 2019 14:59:47
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.63 kb
#include <bits/stdc++.h>
using namespace std;

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

const int N_MAX = 1e5, LOG2_N = 17;

int n, m, x, y;
int rmq[LOG2_N + 2][N_MAX + 2];

int main() {
    in >> n >> m;
    for(int i = 1; i <= n; i++)
        in >> rmq[0][i];

    for(int i = 1; (1 << i) <= n; i++)
        for(int j = 1; j <= n - (1 << i) + 1; j++) {
            rmq[i][j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
        }

    while(m--) {
        in >> x >> y;

        int len = log2(y - x + 1);
        cout << min(rmq[len][x], rmq[len][y - (1 << len) + 1]) << '\n';
    }

    return 0;
}