Pagini recente » Borderou de evaluare (job #337761) | Diferente pentru utilizator/mister_ady intre reviziile 8 si 7 | Istoria paginii utilizator/stargold2 | Cod sursa (job #3148984)
#include <fstream>
using namespace std;
ifstream cin("rmq.in");
ofstream cout("rmq.out");
int r[18][100005],E[100005],n,m,i,j,st,dr;
int p,e,len;
int main()
{
cin>>n>>m;
for(i=1; i<=n; i++)
cin>>r[0][i];
for(p=1; (1<<p)<=n; p++)
{
for(i=1; i<=n; i++)
{
r[p][i]=r[p-1][i];
j=i+(1<<(p-1));
if(j<=n&&r[p][i]>r[p-1][j])
r[p][i]=r[p-1][j];
}
}
E[1]=0;
for(int i=2;i<=n;i++)
E[i]=1+E[i/2];
for(i=1;i<=m;i++)
{
cin>>st>>dr;
e=E[dr-st+1];
len=(1<<e);
cout<<min(r[e][st],r[e][dr-len+1])<<'\n';
}
return 0;
}