Cod sursa(job #1517988)

Utilizator robx12lnLinca Robert robx12ln Data 5 noiembrie 2015 09:33:41
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 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-(1<<k-1);i++){
            D[k][i]=min(D[k-1][i],D[k-1][i+(1<<k-1)]);
        }
    }
    P[1]=0;
    for(i=2;i<=n;i++){
        P[i]=P[i/2]+1;
    }
    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;
}