Cod sursa(job #2624985)
| Utilizator | Data | 5 iunie 2020 17:26:03 | |
|---|---|---|---|
| Problema | Range minimum query | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.55 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("rmq.in");
ofstream g("rmq.out");
int rmq[19][100002], m, n, lg[100002];
int main()
{
f >> n >> m;
for (int i=1;i<=n;i++)
f >> rmq[0][i];
lg[1] = 0;
for (int i=2;i<=n;i++)
lg[i] = lg[i/2]+1;
for(int i=1;(1<<i)<=n;i++)
for(int j=1<<i;j<=n;j++)
rmq[i][j] = min(rmq[i-1][j],rmq[i-1][j-(1<<(i-1))]);
int x,y,l;
for (int i=1;i<=m;i++)
{
f >> x >> y;
l = lg[y-x+1];
g << min(rmq[l][y],rmq[l][x-1+(1<<l)]) << '\n';
}
}
