Cod sursa(job #3372764)

Utilizator Fishy3Petrus Serban Fishy3 Data 4 noiembrie 2026 21:56:05
Problema Range minimum query Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>

using namespace std;

ifstream fin("rmq.in");
ofstream fout("rmq.out");

const int B = 250; //marime unui block
const int INF = 1e9;

int n, m;
int l, r;
int v[100001];
int maxBlock[100001/B + 1];

int main()
{
    fin >> n >> m;

    for(int i = 1;i <= n; i ++)
    {
        fin >> v[i];
    }

    for(int i = 0 ; i < n / B; i ++){
        maxBlock[i] = INF;
    }
    //v[i] apartine grupei i / B
    for(int i = 1 ; i <= n ; i ++){
        maxBlock[i / B] = min(maxBlock[i / B] , v[i]); // elementul minim din block
    }

    for(int i = 1; i <= m; i ++)
    {
        fin >> l >> r;
        int bl = l / B;
        int br = r / B;

        if(bl == br) // daca ii acelasi block merge in O(B)
        {
            int ans = INF;
            for(int i = l ; i <= r; i ++)
            {
                ans = min(ans, v[i]);
            }

            fout << ans << '\n';
        }

        else if(bl < br){
            int ans = INF;
            for(int i = bl + 1; i < br; i ++)
            {
                ans = min(ans , maxBlock[i]);
            }
            //daca o sa mai avem rest intre block uri,tot asa in O(cv(mod B)) ~ O(B)
            for(int i = l; i <= (bl + 1) * B;i ++)
            {
                ans = min(ans , v[i]);
            }
            for(int i = br * B; i <= r; i ++)
            {
                ans = min(ans, v[i]);
            }

            fout << ans << '\n';
        }
    }
    return 0;
}