Cod sursa(job #650887)

Utilizator ChiroscaIrimiaEchipa Chirosca Irimia ChiroscaIrimia Data 19 decembrie 2011 03:19:42
Problema Range minimum query Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.95 kb
#include <stdio.h>
 
long int M[100000][20];
long int n,m;
long int a[100000];

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];
    }

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;
}