Cod sursa(job #3165212)

Utilizator mrvalentynPorumb Valentin mrvalentyn Data 5 noiembrie 2023 17:37:38
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include<bits/stdc++.h>
using namespace std;
#define in ifstream f
#define out ofstream g
#define close f.close();g.close();
#define ll long long
#define intmx INT_MAX
#define intmn INT_MAX*(-1)
in("rmq.in");
out("rmq.out");
int mn[17][100001],n,q;
int e[17];

int main(){
    f>>n;
    for(int i=1;i<=n;++i){
        f>>mn[0][i];
    }
    for(int p=1;(1<<p)<=n;++p)
        for(int i=1;i<=n;++i){
            mn[p][i]=mn[p-1][i];
            int j=i+(1<<(p-1));
            if(j<=n&&mn[p][i]>mn[p-1][j])
                mn[p][i]=mn[p-1][j];
        }

    e[1]=0;
    for(int i=2;i<=n;++i){
        e[i]=1+e[i/2];
    }
    f>>q;
    for(int i=1;i<=q;++i){
        int st,dr;
        f>>st>>dr;
            int exp=e[dr-st+1];
            int len=(1<<exp);
            g<<min(mn[exp][st],mn[exp][dr-len+1])<<endl;
    }
    close return 0;
}