Pagini recente » Rating Robert Beres (robertbombastic) | Diferente pentru preoji/clasament/11-12 intre reviziile 21 si 5 | Cod sursa (job #2473556) | Istoria paginii utilizator/dianahusanu925 | Cod sursa (job #416213)
Cod sursa(job #416213)
//Range Minimum Query
#include <fstream>
using namespace std;
#define NMAX 100002
int A[NMAX],M[NMAX][20];
int main()
{
ifstream fin("rmq.in"); ofstream fout("rmq.out");
int N,m,i,j,k;
fin>>N>>m;
for (i=1;i<=N;++i)
{
fin>>A[i];
M[i][0]=i;
}
for (j=1; 1<<j <= N; ++j)
for (i=1; i+(1<<j)-1 <=N; ++i)
if (A[M[i][j-1]] < A[M[i+(1<<(j-1))][j-1]])
M[i][j]=M[i][j-1];
else M[i][j]=M[i+(1<<(j-1))][j-1];
while (m--)
{ int x,y;
fin>>x>>y;
k=0;
while ((1<<k)<=y-x+1) ++k;
--k;
if (A[M[x][k]]<A[M[y-(1<<k)+1][k]]) fout<<A[M[x][k]]<<"\n";
else fout<<A[M[y-(1<<k)+1][k]]<<"\n";
}
fin.close(); fout.close();
return 0;
}