Cod sursa(job #2885865)
Utilizator | bety bety bety | Data | 6 aprilie 2022 18:23:31 |
---|---|---|---|
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 in("rmq.in");
ofstream out("rmq.out");
const int lim=1e5+4;
int tree[19][lim];
int lg[lim];
int n,q,l,r;
int main()
{
in>>n>>q;
for(int i=1;i<=n;++i)
in>>tree[0][i];
for(int i=2;i<=n;++i)
lg[i]=lg[i/2]+1;
for(int p=1;p<=lg[n];++p)
for(int i=1;i+(1<<p)-1<=n;++i)
tree[p][i]=min(tree[p-1][i],tree[p-1][i+(1<<(p-1))]);
while(q--)
{
in>>l>>r;
int d=lg[r-l+1];
out<<min(tree[d][l],tree[d][r-(1<<d)+1])<<'\n';
}
return 0;
}