Cod sursa(job #1279406)

Utilizator Emil64Emil Centiu Emil64 Data 30 noiembrie 2014 12:05:42
Problema Range minimum query Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<iostream>
#include<fstream>
using namespace std;
int ni,n,i=0,j,m[17][100001]= {0};

int main()
{
    ifstream f("rmq.in");
    ofstream g("rmq.out");
    f>>n>>ni;
    long int p2[18]= {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,121000};
    for(i=1; i<=n; i++)
        f>>m[0][i];
    for(i=1; i<17; i++)
        for(j=1; j<n-i+1; j++)
            if(m[i-1][j]<=m[i-1][j+p2[i-1]])m[i][j]=m[i-1][j];
            else m[i][j]=m[i-1][j+p2[i-1]];
    /*for(i=0;i<=17;i++)
    {
        for(j=1;j<=n-i;j++)
            cout<<m[i][j]<<" ";
        cout<<'\n';
    }*/
    int k=0,x,y;
    for(int t=1; t<=ni; t++)
    {
        f>>x>>y;
        while(p2[k]<=y-x+1)k++;
        --k;
        if(m[k][x]<m[k][x+1])
            g<<m[k][x]<<'\n';
        else g<<m[k][x+1]<<'\n';
    }
}