Cod sursa(job #1918735)
Utilizator | Jordan jordan1998 | Data | 9 martie 2017 16:42:14 |
---|---|---|---|
Problema | Range minimum query | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include <fstream>
using namespace std;
int n,m,i,arb[200005],x,a,b;
int main()
{
ifstream f("rmq.in");
ofstream g("rmq.out");
f>>n>>m;
for(i=0;i<n;i++)
f>>arb[i+n];
for(i=n-1;i>0;i--)
arb[i]=min(arb[i*2],arb[i*2+1]);
for(i=1;i<=m;i++)
{
f>>a>>b;a+=n-1;b+=n-1;
x=200000000;
for(;a<=b;)
{ x=min(x,min(arb[a],arb[b]));
b=(b-1)/2;
a=(a+1)/2;
}
g<<x<<'\n';
}
}