Cod sursa(job #2455555)

Utilizator anamariatoaderAna-Maria Toader anamariatoader Data 11 septembrie 2019 22:00:46
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <cmath>
#define DIM 100005

using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");

int n,m,i,j,x,y,v[DIM],a[DIM][105];

int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>v[i];
        a[i][0]=i;
    }
    int q=sqrt(n);
    for(j=1;j<=q;j++)
     for(i=1;i+(1<<(j-1))<=n;i++){
        if(v[a[i][j-1]]<v[a[i+(1<<(j-1))][j-1]])
            a[i][j]=a[i][j-1];
        else
            a[i][j]=a[i+(1<<(j-1))][j-1];
     }
    for(i=1;i<=m;i++){
        fin>>x>>y;
        int l=y-x+1;
        int k=(l&(-l));
        if(k==l){
            k=0; int p=1;
            while(p*2<=l){
                k++;
                p*=2;
            }
        }
        if(x+(1<<k)-1==y)
            fout<<v[a[x][k]]<<'\n';
        else
            fout<<min(v[a[x][k]],v[y])<<'\n';
    }
    return 0;
}