Cod sursa(job #1201519)
Utilizator | cont-vechi azkaban | Data | 25 iunie 2014 13:01:04 |
---|---|---|---|
Problema | Range minimum query | Scor | 20 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
using namespace std;
ifstream cin("rmq.in");
ofstream cout("rmq.out");
int n,i,m,j,k,a,b,aux;
int RMQ[33][100013];
int main()
{
cin>>n>>m;
for (i=1;i<=n;++i) cin>>RMQ[0][i];
for (i=1;(1<<i)<=n;++i)
for (j=1;j+(1<<i)-1<=n;++j)
RMQ[i][j]=min(RMQ[i-1][j],RMQ[i-1][j+(1<<i-1)]);
for (i=1;i<=m;++i){
k=0;
cin>>a>>b;
for (aux=1; aux<=(b-a); aux*=2) ++k;
--k;
cout<<min(RMQ[k][a],RMQ[k][b-(1<<k)+1])<<"\n";
}
return 0;
}