Pagini recente » Cod sursa (job #1127207) | Cod sursa (job #631399) | Cod sursa (job #437408) | Cod sursa (job #2701886) | Cod sursa (job #2110052)
#include <bits/stdc++.h>
#define nmax 1000003
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int rmq[18][nmax];
int P[nmax],n;
void Puteri()
{
P[1]=0;
for(int i=2; i<=n; i++)
P[i]=1+P[i/2];
}
void RMQ()
{
int i,j,L;
L=P[n];
for(i=1; i<=L; i++)
for(j=1; j<=n-(1<<i)+1; j++)
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
}
int main()
{
int i,Q,x,y,len;
fin>>n>>Q;
for(i=1; i<=n; i++)
fin>>rmq[0][i];
Puteri();
RMQ();
while(Q--)
{
fin>>x>>y;
len=P[y-x+1];
fout<<min(rmq[len][x],rmq[len][y+1-(1<<len)])<<"\n";
}
return 0;
}