Cod sursa(job #1685633)

Utilizator daGramaGrama Matei daGrama Data 11 aprilie 2016 19:37:12
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int N = 100000,
          M = 1000000;

int n,m;
int r[N+1][18],v[N];
int log[N];
int rez;

int main()
{
    int x,y,L;
    f>>n>>m;
    for(int i=1;i<=n;i++){
        f>>v[i];
    }

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


    /// r[i][j] = minim din intervalul [ i- 2^j+1 , i]
    /// r[i][j] = v[i] daca j=0
    ///           min( r[i][j-1], r[i-(1<<(j-1))][j-1])

    for(int i=1;i<=n;i++){
        r[i][0] = v[i];
    }

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


    for(int i=1;i<=m;i++){
        f>>x>>y;
        L=log[y-x+1];
        rez=min(r[y][L],r[x+(1<<L)-1][L]);
        g<<rez<<'\n';
    }
    return 0;
}