Cod sursa(job #2458638)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 21 septembrie 2019 11:23:18
Problema Range minimum query Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>

using namespace std;

char Advance()
{
        if(pointer == SIZE)
        {
                fread(buffer, 1, SIZE, stdin);
                pointer = 0;
        }
        return buffer[pointer++];
}

int Read()
{
        int Ans = 0;
        char ch = Advance();
        while(!isdigit(ch))
                ch = Advance();
        while(isdigit(ch))
        {
                Ans = 10 * Ans + (ch - '0');
                ch = Advance();
        }
        return Ans;
}

const int N = 100000+7;
const int LG = 17;

int RMQ[N][LG];
int Log[N];

int main()
{
        freeopen("rmq.in", "r", stdin);
        freeopen("rmq.out", "w", stdout);
        int n, q;
        n = Read();
        q = Read();

        for(int i = i; i <= n; i++) {
            RMQ[i][0] = Read();
        }
        for(int i = 2; i <= n; i++) {
            Log[i] = 1 + Log[(i>>1)];
        }

        for(int k = 1; (1 << k) <= n; k++) {
            for(int i = 1; i + (1 << k) <= n; i++) {
                RMG[i][k] = min(RMQ[i][k-1], RMQ[i+(1 << (k-1))][k-1]);
            }
        }

        for(int i = 0; i < q; i++) {
            int l = Read(), r = Read();
            int k = Log[r-l+1];
            int out = min(RMQ[l][k], RMQ[r - (1 << k) + 1][k]);
            printf("%d\n", out);
        }
}