Cod sursa(job #333538)

Utilizator levap1506Gutu Pavel levap1506 Data 23 iulie 2009 10:05:26
Problema Range minimum query Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
int M[100010][20],A[100010],i,N,m,j,a,b;
int main() {
      ifstream in;
      ofstream out;
      in.open("rmq.in");
      out.open("rmq.out");
      in >> N >> m;
      for (i=0;i<N;i++) {
          in >> A[i];
          M[i][0]=A[i];
      }


      for (j = 1; (1 << j) <= N; j++)
          for (i = 0; i + (1 << j) - 1 < N; i++)
              if (M[i][j - 1] <= M[i + (1 << (j - 1))][j - 1])
                  M[i][j] = M[i][j - 1];
              else
                  M[i][j] = M[i + (1 << (j - 1))][j - 1];

       for (int x=0; x<m; x++) {
           in >> i >> j;
           i--; j--;
            int k=(int)(log(j-i+1)/log(2));
            if (M[i][k]<=M[j-(1<<k)+1][k])
            {
                out << M[i][k] << "\n";
            }
            else
            {
                out << M[j-(1<<k)+1][k] << "\n";
            }
       }
       out.close();
}