Cod sursa(job #2175394)
Utilizator | Mihalut Filip filip.mihalut | Data | 16 martie 2018 16:58:55 |
---|---|---|---|
Problema | Range minimum query | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream f ("rmq.in");
ofstream g ("rmq.out");
int a[20][Nmax] , n ,t,i,k,m,x,y,j;
int main()
{
f >> n >> t;
for(i = 1;i <= n;i++)
f >> a[0][i];
k = 1;
m = log2(n);
for(i = 1;i <= m;i++)
{
for(j = 1;j <= n - 2*k + 1;j++)
a[i][j] = min(a[i - 1][j],a[i - 1][j + k]);
k *= 2;
}
for(i = 1;i <= t;i++)
{
f >> x >> y;
k = log2(y - x + 1);
m = pow(2,k);
g << min(a[k][x] , a[k][y - m + 1]) << '\n';
}
return 0;
}