Cod sursa(job #2203735)

Utilizator Vlad_lsc2008Lungu Vlad Vlad_lsc2008 Data 12 mai 2018 23:42:04
Problema Range minimum query Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <iostream>
#include <fstream>
using namespace std;

int m,n;
int log[100010];
int put[25];
int rmq[100010][25];

int main()
{
    ifstream t1("rmq.in");
    ofstream t2("rmq.out");
    int i,j;
    t1>>n>>m;
    put[0]=1;
    for(i=1;i<=20;i++) put[i]=2*put[i-1];
    for(i=2;i<=n;i++) log[i]=log[i/2]+1;

    for(i=1;i<=n;i++) t1>>rmq[i][0];

    for( j=1; put[j]<=n;j++)
        for(i=1; i+put[j]-1 <=n;i++)
            rmq[i][j]= min( rmq[i][j-1] , rmq[i+ put[j-1]][j-1] );

    int a,b,l;
    for(i=1;i<=n;i++)
    {
        t1>>a>>b;
        l=log[b-a+1];
        t2<<min( rmq[a][l], rmq[ b- put[l]+1 ][l] )<<'\n';
    }

    t1.close();
    t2.close();
    return 0;
}