Cod sursa(job #2527743)
| Utilizator | Data | 20 ianuarie 2020 20:41:14 | |
|---|---|---|---|
| Problema | Range minimum query | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.57 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
const int NMAX=1e5;
int n,m,v[NMAX+7],a[20][NMAX+7];
int main()
{
fin >> n >> m;
for(int i=1;i<=n;i++)
fin >> v[i], a[0][i]=v[i];
for(int i=1;(1<<i)<=n;i++)
for(int j=1;j<=(n-(1<<i)+1);j++)
a[i][j]=min(a[i-1][j],a[i-1][j+(1<<(i-1))]);
for(;m;m--)
{
int x,y;
fin >> x >> y;
int l=log(y-x+1)/log(2);
fout << min(a[l][x],a[l][y+1-(1<<l)]) << "\n";
}
return 0;
}
