Cod sursa(job #2623347)
Utilizator | Data | 2 iunie 2020 23:38:11 | |
---|---|---|---|
Problema | Range minimum query | Scor | 40 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <bits/stdc++.h>
#define N 100002
using namespace std;
int lg[N],rmq[20][N],a,b;
int main()
{
ifstream f("rmq.in");
ofstream g("rmq.out");
int n,m,i,j,x,l;
f>>n>>m;
for(i=0 ; i<n; i++)
f>>rmq[0][i];
lg[1]=0;
for (i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
for(i = 1 ; (1<<i) <= n ; i++)
for(j = 0 ; j + (1 << i) - 1 < n ; j++)
rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);
for(i=0 ; i<m; i++)
{
f>>a>>b;
l=lg[b-a+1];
x=b-(1<<l);
g<< min(rmq[l][a-1],rmq[l][x])<<endl;
}
return 0;
}