Cod sursa(job #161220)

Utilizator ViksenVictor-Nicolae Savu Viksen Data 17 martie 2008 19:12:40
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <iostream>
#define FIN "rmq.in"
#define FOUT "rmq.out"

int A[18][100000],n,m,i,k;

int min(int x, int y) {return (x<y)?(x):(y);}

int log ( int x ) { return (x>1)?(log(x>>1)+1):(0); }

int main()
{
    freopen ( FIN , "r" , stdin );
   freopen ( FOUT , "w" , stdout );

    scanf ( "%d %d" , &n , &m );
    for ( i=0 ; i<n ; i++ ) 
        scanf ( "%d" , &A[0][i] );

    for (  k=1 ; 1<<k < n ; k++ )
        for (i=0 ; i + (1<<k) -1 < n ; i++)
            A[k][i] = min ( A[k-1][i] , A[k-1][i + (1<<(k-1))] );

    int j;
    while (m--)
    {
        scanf ("%d %d" , &i , &j );i--;j--;
        k = log(j-i+1);
        printf ( "%d\n" , min ( A[k][i] , A[k][j-(1<<k)+1] ) );
    }

    fclose ( stdin );
    fclose ( stdout );
    return 0;
}