Cod sursa(job #1897111)

Utilizator claudiuarseneClaudiu Arsene claudiuarsene Data 1 martie 2017 10:10:23
Problema Range minimum query Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include<cstdio>
using namespace std;
int j,d,n,m,v[100001],b[20][100001],i,s,t;
int min(int x,int y)
{
    if (x>y) return y;
    else return x;
}
int main()
{
    freopen("rmq.in","r",stdin);
    freopen("rmq.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    for(i=1;i<=n;i++)
        b[1][i]=v[i];
    int p=1,nr=0;
    p=1;
    for (i=2;i<=20;i++)
    {
        p=p*2;
        for (j=1;j+p<=n+1;j++)
            b[i][j]=min(b[i-1][j],b[i-1][j+p/2]);
        t=i;
        if (p>n) break;
    }
    int x,y,z,l;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        z=y-x+1;
        p=1;
        l=0;
        while(p<=z)
        {
            p=p*2;
            l++;
        }
        p=p/2;
        printf("%d\n",min(b[l][x],b[l][y-p+1]));
    }
 /*   printf("\n");
    for(i=1;i<=t;i++)
    {
        for(j=1;j<=n;j++)
            printf("%d ",b[i][j]);
        printf("\n");
    }
    */
    return 0;
}