Pagini recente » Cod sursa (job #2538105) | Cod sursa (job #1391693) | Cod sursa (job #930905) | Cod sursa (job #2538212) | Cod sursa (job #650889)
Cod sursa(job #650889)
#include<stdio.h>
#include<math.h>
long int M[100005][20];
long int n,m;
long int a[100005],logaritm[100005];
long int min(long int a, long int b)
{
if(a<b)
return a;
return b;
}
/*int logaritm(long int x)
{
int i;
for(i=0;i<=20;i++)
{
if(pow(2,i)==x) return i;
if(pow(2,i)>x) return i-1;
}
}
*/
int main()
{
FILE *f,*g;
f = fopen("rmq.in","r");
g = fopen("rmq.out","w");
int i,j,l;
long int x,y,p,lungime;
fscanf(f,"%ld %ld",&n,&m);
for(i=1;i<=n;i++)
{
fscanf(f,"%ld ",&a[i]);
M[i][0]=a[i];
}
logaritm[1]=0;
for(i=2;i<n;i++)
logaritm[i]=logaritm[i/2]+1;
for(i=1;(1<<i)<=n;i++)
{
l=1<<((i-1));
for (j=1;j<=n-(1<<i)+1;j++)
M[j][i]=min(M[j][i-1],M[j+l][i-1]);
}
for(i=1;i<=m;i++)
{
fscanf(f,"%ld %ld",&x,&y);
lungime=y-x+1;
l=logaritm[lungime];
p=lungime-(1<<l);
fprintf(g,"%ld\n",min(M[x][l],M[x+p][l]) );
}
fclose(f);
fclose(g);
return 0;
}