Cod sursa(job #2170825)
Utilizator | Alexandrina Panfil wilson182 | Data | 15 martie 2018 09:53:40 |
---|---|---|---|
Problema | Range minimum query | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.42 kb |
#include<bits/stdc++.h>
using namespace std;
int a[20][100020];
int main(){
int n,m,x,y;
ifstream f("rmq.in");
ofstream g("rmq.out");
f>>n>>m;
for(int i=1;i<=n;i++)f>>a[0][i];
for(int i=1;(1<<i)<=n;i++){
int p=(1<<(i-1)),k=n-(1<<i)+1;
for(int j=1;j<=k;j++){
a[i][j]=min(a[i-1][j],a[i-1][j+p]);
}
}
while(m--){
f>>x>>y;
int c=log(y-x+1)/log(2);
g<<min(a[c][x],a[c][y-(1<<c)+1])<<'\n';
}
}