Cod sursa(job #2110052)

Utilizator Petru00Octavian Petrut Petru00 Data 20 ianuarie 2018 12:13:17
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <bits/stdc++.h>
#define nmax 1000003
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
int rmq[18][nmax];
int P[nmax],n;
void Puteri()
{
    P[1]=0;
    for(int i=2; i<=n; i++)
        P[i]=1+P[i/2];
}
void RMQ()
{
    int i,j,L;
    L=P[n];
    for(i=1; i<=L; i++)
        for(j=1; j<=n-(1<<i)+1; j++)
            rmq[i][j]=min(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);

}
int main()
{
    int i,Q,x,y,len;
    fin>>n>>Q;
    for(i=1; i<=n; i++)
        fin>>rmq[0][i];
    Puteri();
    RMQ();
    while(Q--)
    {
        fin>>x>>y;
        len=P[y-x+1];
        fout<<min(rmq[len][x],rmq[len][y+1-(1<<len)])<<"\n";
    }
    return 0;
}