Cod sursa(job #2291857)
Utilizator | Rosca Rares Raresr14 | Data | 28 noiembrie 2018 18:26:07 |
---|---|---|---|
Problema | Range minimum query | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include <fstream>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int n,m,i,j,p,D[102][100002],L[100002],a,b,log;
int main(){
fin>>n>>m;
for(i=1;i<=n;i++)
fin>>D[0][i];
for(i=1;(1<<i)<=n;i++)
for(j=1;j<=n;j++){
D[i][j]=D[i-1][j];
if(j+(1<<(i-1))<=n&&D[i-1][j+(1<<(i-1))]<D[i][j])
D[i][j]=D[i-1][j+(1<<(i-1))];
}
for(i=2;i<=n;i++)
L[i]=1+L[i>>1];
for(;m--;){
fin>>a>>b;
log=L[b-a+1];
fout<<min(D[log][a],D[log][b-(1<<log)+1])<<"\n";
}
return 0;
}