Cod sursa(job #2764271)
| Utilizator | Data | 20 iulie 2021 10:18:41 | |
|---|---|---|---|
| Problema | Range minimum query | Scor | 100 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva educationala | Marime | 0.63 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int N,M,x,lg[100005],D[105][100005],y,i,j,a,b,k;
int main()
{
fin>>N>>M;
for(i=1; i<=N; i++)
{
fin>>x;
D[0][i]=x;
}
lg[1]=0;
for(i=2; i<=100005; i++) lg[i]=lg[i/2]+1;
for(i=1; i<=lg[N]; i++)
{
for(j=1; j<=N; j++)
{
y=1<<(i-1);
D[i][j]=min(D[i-1][j],D[i-1][j+y]);
}
}
for(i=1; i<=M; i++)
{
fin>>a>>b;
k=lg[b-a];
fout<<min(D[k][a],D[k][b-(1<<(k))+1])<< '\n';
}
return 0;
}
