Cod sursa(job #2775964)

Utilizator gripzStroescu Matei Alexandru gripz Data 18 septembrie 2021 12:46:39
Problema Range minimum query Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <climits>

#define MAXN 100001
#define LOG 18

using namespace std;


int N, M;
int v[MAXN], rmq[2*MAXN][LOG], log[MAXN];
int x, y;

int main() {
    freopen("rmq.in", "r", stdin);
    freopen("rmq.out", "w", stdout);

    cin >> N >> M;

    for(int i = 1; i <= N; i++) {
        cin >> v[i];
        rmq[i][0] = v[i];
    }

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

    log[0] = log[1] = 0;

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

    for(int i = 1; i <= M; i++) {
        cin >> x >> y;
        int L = log[y-x+1];
        cout << min(rmq[x][L], rmq[y -(1 << L) + 1][L]);
        cout << endl;
    }
}