Mai intai trebuie sa te autentifici.
Cod sursa(job #2901431)
| Utilizator | Data | 13 mai 2022 18:34:18 | |
|---|---|---|---|
| Problema | Range minimum query | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.55 kb |
#include <bits/stdc++.h>
using namespace std;
int m,n,lg[100002],rmq[20][100002],x,y,lgg;
int main(){
ifstream f("rmq.in");
ofstream g("rmq.out");
lg[1]=0;
f>>n>>m;
for(int i=2;i<=n;++i)
lg[i]=1+lg[i/2];
for(int i=1;i<=n;++i)
f>>rmq[0][i];
for(int i=1;i<=lg[n];++i)
for(int j=1;j+(1<<i)<=n+1;++j)
rmq[i][j]= min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
for(int i=1;i<=m;++i){
f>>x>>y;
lgg=lg[y-x+1];
g<<min(rmq[lgg][x],rmq[lgg][y-(1<<lgg)+1])<<'\n';
}
return 0;
}