Cod sursa(job #2465115)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 29 septembrie 2019 14:16:53
Problema Range minimum query Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <math.h>

using namespace std;

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

struct interval
{
    int x, y;
};

interval q[1000009];

void citire();
void afisare();

int n, m, i, j, x, lg;
int a[21][100009], v[1000009], putere2[18];

int main()
{
    citire();

    x = log2 ( n );
    putere2[0] = 1;
    for ( i = 1 ; i <= x ; i++ ) putere2[i] = 1 << i;

    for ( i = 1 ; i <= n ; i++ ) a[0][i] = v[i];
    for ( i = 1 ; i <= x ; i++ )
        for ( j = 1 ; j <= n - putere2[i] + 1 ; j++ )
            a[i][j] = min ( a[i-1][j], a[i-1][j+putere2[i-1]] );

    for ( i = 1 ; i <= m ; i++ )
    {
        lg = q[i].y - q[i].x + 1;
        x = log2 ( lg );
        fout << min ( a[x][q[i].x], a[x][q[i].y-putere2[x]+1] ) << '\n';
    }

    return 0;
}

void citire()
{
    fin >> n >> m;
    for ( i = 1 ; i <= n ; i++ ) fin >> v[i];
    for ( i = 1 ; i <= m ; i++ ) fin >> q[i].x >> q[i].y;
}