Cod sursa(job #3255514)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 10 noiembrie 2024 20:12:38
Problema Range minimum query Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.6 kb
#include <fstream>
using namespace std;
ifstream cin("rmq.in");
ofstream cout("rmq.out");
int n,q,x,y,a[20][100001],p[100001];
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>a[0][i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n;j++){
            a[i][j]=a[i-1][j];
            if((1<<(i-1))+j<=n)
                a[i][j]=min(a[i][j],a[i-1][(1<<(i-1))+j]);
        }
    for(int i=2;i<=n;i++)
        p[i]=p[i/2]+1;
    while(q--){
        cin>>x>>y;
        int exp=p[y-x+1];
        cout<<min(a[exp][x],a[exp][y-(1<<exp)+1])<<'\n';
    }
    return 0;
}