Cod sursa(job #1217919)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 8 august 2014 19:02:12
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
using namespace std;

ifstream cin("rmq.in");
ofstream cout("rmq.out");

const int nmax = 100010;

int n,m,a[nmax],rmq[nmax][20],lg[nmax];
int main()
{
    cin>>n>>m;
    int i,j;
    for (i=1;i<=n;i++) cin>>a[i];

    //preprocesarea
    for (i=1;i<=n;i++) rmq[i][0]=i;
    for (j=1;(1<<j)<=n;j++)
        for (i=1; (i+(1<<j)-1<=n);i++)
          if (a[rmq[i][j-1]]<a[rmq[i+(1<<(j-1))][j-1]])
            rmq[i][j]=rmq[i][j-1];
             else rmq[i][j]=rmq[i+(1<<(j-1))][j-1];

    while (m--)
    {
        int i,j;
        cin>>i>>j;
        int k=0;
        while ((1<<k)<=(j-i+1)) k++; k--;
        cout<<min(a[rmq[i][k]],a[rmq[j-(1<<k)+1][k]])<<"\n";
    }
    return 0;

}