rmq accepted

 avatar
unknown
c_cpp
25 days ago
1.1 kB
6
Indexable
/*
in the name of coder of the world
    * ANAR *
*/
#include<iostream>
using namespace std;
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'

int mysq(int n){
    int l = 1, r = n/2, mid;
    while(r - l > 1){
        mid = (l+r) / 2;
        if(mid * mid <= n)
            l = mid;
        else
            r = mid;
    }
    return l;
}

int main(){
    ios;

    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    int bl[n], sq = mysq(n);
    for(int i = 0; i < n; i++)
        bl[i] = 2147483647 ;
    for(int i = 0; i < n; i++){
        bl[i/sq] = min(a[i], bl[i/sq]);
    }
    int q;
    cin >> q;
    while(q--){
        int l, r, ans = 2147483647;
        cin >> l >> r;
        while(l <= r){
            if(!(l % sq) && l + sq <= r){
                ans = min(bl[l/sq], ans);
                l += sq;
            }
            else{
                ans = min(ans, a[l]);
                l++;
            }
        }
        cout << ans << endl;
    }



    return 0;
}
Editor is loading...
Leave a Comment