Cod sursa(job #2500941)
Utilizator | Data | 28 noiembrie 2019 21:12:38 | |
---|---|---|---|
Problema | Range minimum query | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <fstream>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int i,j,L[100010],D[17][100010],a,b,q,n;
int main(){
fin>>n>>q;
for(i=1;i<=n;i++)
fin>>D[0][i];
for(i=1;(1<<i)<=n;i++)
for(j=1;j<=n;j++){
D[i][j]=D[i-1][j];
if(D[i-1][j+(1<<(i-1))]<D[i-1][j]&&(j+(1<<(i-1)))<=n)
D[i][j]=D[i-1][j+(1<<(i-1))];
}
for(i=2;i<=n;i++)
L[i]=1+L[i/2];
for(;q--;){
fin>>a>>b;
int l=L[b-a+1];
fout<<min(D[l][a],D[l][b-(1<<l)+1])<<"\n";
}
return 0;
}