Cod sursa(job #2306203)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 21 decembrie 2018 19:13:19
Problema Range minimum query Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.49 kb
#include<stdio.h>
#define N(x,y) (a[x]<a[y]?x:y)
int n,m,a[100001],i,j,b[100001][18],k,x,y,c[100001];
int main() 
{
    freopen("rmq.in","r",stdin),freopen("rmq.out","w",stdout),scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]),b[i][0]=i,c[i+1]=c[(i+1)/2]+1;
    for(j=1;(1<<j)<=n;j++)
    	for(i=0;i+(1<<j)-1<n;i++)
        	b[i][j]=N(b[i][j-1],b[i+(1<<(j-1))][j-1]);
    while(m--) 
        scanf("%d%d",&x,&y),k=c[y-x+1],printf("%d\n",a[N(b[x-1][k],b[y-(1<<k)][k])]);
}