Pagini recente » Cod sursa (job #2452380) | Istoria paginii utilizator/lovaszkarla | Rating Carcea Paul (paulyoo) | Cod sursa (job #1463359) | Cod sursa (job #1330764)
#include <fstream>
#define DIM 100002
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int N,D[DIM][30],log[DIM],a,b,M,x;
int main(){
fin>>N>>M;
for(int i=2;i<=N;i++)
log[i]=log[i/2]+1;
for(int i=1;i<=N;i++)
fin>>D[0][i];
for(int i=1;i<=log[N]+1;i++)
for(int j=1;j<=N;j++)
D[i][j]=min(D[i-1][j],D[i-1][j+(1<<(i-1))]);
for(int i=1;i<=M;i++){
fin>>a>>b;
x=log[b-a+1];
fout<<min(D[x][a],D[x][b-(1<<x)+1])<<"\n";
}
fin.close();fout.close();
return 0;
}