Cod sursa(job #2055111)
Utilizator | Data | 2 noiembrie 2017 20:47:27 | |
---|---|---|---|
Problema | Range minimum query | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.53 kb |
#include <fstream>
#include <cmath>
using namespace std;
ifstream fin ("rmq.in");
ofstream fout ("rmq.out");
int n,i,j,a[33][100001],c,m,t,x,y,k;
int main(){
fin>>n>>m;
for(i=1;i<=n;i++){
fin>>a[0][i];
}
for(i=1;i<=n;i++){
c=1<<i;
for(j=1;j<=n-c+1;j++){
a[i][j]=min(a[i-1][j],a[i-1][j+c-1]);
}
}
for(t=1;t<=m;t++){
fin>>x>>y;
c=1<<((int)(log2(y-x+1)));
k=(int)(log2(y-x+1));
fout<<min(a[k][x],a[k][y-c+1])<<"\n";
}
}