Cod sursa(job #833647)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 12 decembrie 2012 21:00:18
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#define MAX_SIZE 100000


using namespace std;

int matrix[18][MAX_SIZE];
int lg[MAX_SIZE];


int minim(int a , int b)
{
    if (a < b) return a;
    else return b;
}

int main()
{
    ifstream input("rmq.in");
    ofstream output("rmq.out");
    int N , M;
    input >> N >> M;
    int logN = 1;
    while ( (1 << logN) < N)
    {
        logN ++;
    }
    logN --;

    lg[1] = 0;
    for (int i = 2 ; i <= N;i++)
    {
        lg[ i ] = lg[i/2] + 1;
    }

    for (int i = 1;i <= N;i++)
    {
        input >> matrix[0][i];
    }
    for (int i = 1 ; i <= logN;i++)
        for (int j = 1;j<=N - ( 1 << i) + 1;j++)
        {
            matrix[i][j] = minim(matrix[i-1][j] , matrix[i-1][j+(1 << (i-1))]);
        }
    for (int i = 0 ; i< M;i++)
    {
        int x , y;
        input >> x >> y;
        int t = y - x + 1;
        int l = lg[t];
        t = t - ( 1 << l);
        output << minim( matrix[l][x] , matrix[l][x+t]) << "\n";


    }
    input.close();
    output.close();




    return 0;
}