Cod sursa(job #2342481)

Utilizator AndreiTurcasTurcas Andrei AndreiTurcas Data 12 februarie 2019 20:54:55
Problema Range minimum query Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#define lim 100001
using namespace std;

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

int n, m, v[lim], rmq[lim][20], Lg[lim];

void preprocess()
{
    for(int i = 2; i <= n; ++i)
        Lg[i] = Lg[i>>1] + 1;
    for(int i = 1; i <= n; ++i)
        rmq[i][0] = i;
    for(int j = 1; (1<<j) < n; ++j)
        for(int i = 1; i+(1<<j)-1 <= n; ++i)
            if(v[rmq[i][j-1]] < v[rmq[i+(1<<(j-1))][j-1]])
                rmq[i][j] = rmq[i][j-1];
            else
                rmq[i][j] = rmq[i+(1<<(j-1))][j-1];
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; ++i)
        f >> v[i];
    preprocess();
    for(int i = 1; i <= m; ++i)
    {
        int x, y, lg, sol;
        f >> x >> y;
        lg = Lg[y-x+1];
        if(v[rmq[x][lg]] < v[rmq[y-(1<<lg)+1][lg]])
            sol = rmq[x][lg];
        else
            sol = rmq[y-(1<<lg)+1][lg];
        g << v[sol] << "\n";
    }
}