Cod sursa(job #563535)
Utilizator | Bacila Emilian bacila | Data | 25 martie 2011 13:17:35 |
---|---|---|---|
Problema | Range minimum query | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.47 kb |
#include<fstream>
#include<cmath>
using namespace std;
int v[100005][20],n,i,j,x,y,m,k;
int mini(int q,int w)
{
if(q<w)
return q;
return w;
}
int main()
{ifstream f("rmq.in");
f>>n>>m;
for(i=1;i<=n;i++)
f>>v[i][0];
ofstream g("rmq.out");
for(i=1;(1<<i)<=n;i++)
for(j=1;j+i<=n;j++)
v[j][i]=mini(v[j][i-1],v[j+(1<<(i-1))][i-1]);
for(i=1;i<=m;i++)
{ f>>x>>y;
k=31-__builtin_clz(y-x+1);
g<<mini(v[x][k],v[y-(1<<k)+1][k])<<'\n';
}
return 0;
}