Cod sursa(job #2268274)
| Utilizator | Data | 24 octombrie 2018 17:17:26 | |
|---|---|---|---|
| Problema | Range minimum query | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.54 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("rmq.in");
ofstream g("rmq.out");
const int N=100010;
int n,m,a[17][N];
int main()
{
f>>n>>m;
for(int i=1;i<=n;i++)f>>a[0][i];
for(int i=1,p=1,P=2;P<=n;i++,p*=2,P*=2)
for(int st=1,mi=p+1,dr=P;dr<=n;st++,mi++,dr++)
a[i][st]=min(a[i-1][st],a[i-1][mi]);
for(;m;m--)
{
int x,y;
f>>x>>y;
int i=31-__builtin_clz(y-x+1);
int p=1<<i;
g<<min(a[i][x],a[i][y-p+1])<<'\n';
}
return 0;
}
