Cod sursa(job #1501682)

Utilizator robx12lnLinca Robert robx12ln Data 13 octombrie 2015 18:54:47
Problema Range minimum query Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<fstream>
#define DIM 100005
using namespace std;
ifstream fin ("rmq.in");
ofstream fout("rmq.out");
int D[17][DIM],P[DIM],n,m,i,k,p,a,b;
int main(){
    fin>>n>>m;
    for(i=1;i<=n;i++){
        fin>>D[0][i];
    }
    //D[k][i]=min(D[k-1][i],D[k-1][i+2^k-1];
    for(k=1;(1<<k)<=n;k++){
        for(i=1;i<=n;i++){
            D[k][i]=D[k-1][i];
            if(i+(1<<k-1)<=n){
                D[k][i]=min(D[k][i],D[k-1][i+(1<<k-1)]);
            }
        }
    }
    P[1]=1;
    p=1;
    for(i=2;i<=n;i++){
        if(p*2==i){
            P[i]=1;
            p*=2;
        }
    }
    for(i=1;i<=m;i++){
        fin>>a>>b;
        p=P[b-a+1];
        fout<<min(D[p][a],D[p][b-(1<<p)+1])<<"\n";
    }
    return 0;
}