View Code of Problem 134

#include <stdio.h>
#include <math.h>
#include <malloc.h>
#define N 100000+10
int dp[N][17];
int a[N];
int min(int a,int b){
	int t;
	if(a > b){
		t = a;a = b;b =t;
	}
	return a;
}
void st(int a[N],int n){
	int i,j,m;	
	for(i = 1;i<=n;i++)
		dp[i][0] = a[i];
	m = (int)(log((double)(n))/log(2.0));
	for(j = 1;j<=m;j++){
		for(i =1;i+(1<<j)-1<=n;i++)
			dp[i][j] = min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
	}
	return;
}
int find(int l,int r){
	int k = (int)(log((double)(r-l+1))/log(2.0));
	printf("%d\n",min(dp[l][k],dp[r-(1<<k)+1][k]));
	return 0;
}
main(){
	int n,i,m,x,y,t;
	scanf("%d",&n);
	for(i = 1; i<=n; i++)
		scanf("%d",a+i);
	st(a,n);
	scanf("%d",&m);
	while(m > 0){
		scanf("%d%d",&x,&y);
		if(y < x){
			t =x;x=y;y=t;
		}
		find(x,y);
		m--;
	}
	return 0;
}

Double click to view unformatted code.


Back to problem 134