Cod sursa(job #2455558)

Utilizator anamariatoaderAna-Maria Toader anamariatoader Data 11 septembrie 2019 22:10:38
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 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][320];

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=0;
        while((1<<(k+1))<=l)
            k++;
        int rez=0;
        if(x+(1<<k)-1==y)
            rez = v[a[x][k]];
        else
            rez = min(v[a[x][k]],v[a[x+(1<<k)-1][k]]);
        fout<<rez<<'\n';
    }
    return 0;
}