Cod sursa(job #2593041)

Utilizator bl1nk3rFilip Corlan bl1nk3r Data 2 aprilie 2020 19:37:13
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>

using namespace std;

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

int rmq[20][100001];
int log[100001];

int main() {
    int n, k;
    in >> n >> k;

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

    log[1] = 0;

    for (int i = 2; i <= n; i++) {
        log[i] = 1 + log[i / 2];
    }

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

    for (int i = 0; i < k; i++) {
        int low, high;
        in >> low >> high;

        int l = log[high - low];
        out << min(rmq[l][low + (1 << l) - 1], rmq[l][high]) << " ";
    }

    return 0;
}