Cod sursa(job #1712802)
Utilizator | Data | 3 iunie 2016 19:07:16 | |
---|---|---|---|
Problema | Range minimum query | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.56 kb |
#include <fstream>
using namespace std;
ifstream f("rmq.in");
ofstream g("rmq.out");
int n,i,m,r[17][100010],b[100010],L,R,p,q;
int main()
{
f>>n>>m;
for(i=1;i<=n;i++)
f>>r[0][i];
for(i=1,p=1,q=2;q<=n;i++,p<<=1,q<<=1)
for(L=1,R=q;R<=n;L++,R++)
r[i][L]=min(r[i-1][L],r[i-1][L+p]);
for(q=2;q<=n;q<<=1)
b[q]=1;
for(i=1;i<=n;i++)
b[i]+=b[i-1];
for(;m;m--)
{
f>>L>>R;
p=b[R-L+1];
q=1<<p;
g<<min(r[p][L],r[p][R-q+1])<<"\n";
}
return 0;
}