Pagini recente » Borderou de evaluare (job #635012) | Istoria paginii runda/antr2/clasament | Cod sursa (job #446640) | Autentificare | Cod sursa (job #650868)
Cod sursa(job #650868)
#include<stdio.h>
#define NMAX 100001
#define LMAX 17
long int v[NMAX], M[LMAX][NMAX],lg[NMAX];
long int min(long a, long b)
{
if(b<a)
return b;
return a;
}
int main()
{
long int n,m,x,y,i,j,aux,lung, linie;
FILE *input,*output;
input=fopen("rmq.in","r");
fscanf(input,"%ld",&n);
fscanf(input,"%ld",&m);
for (i=1;i<=n;i++)
fscanf(input,"%ld ",&v[i]);
for (i=1;i<=n;i++)
M[0][i]=v[i];
for (i=1;(1<<i)<=n;i++)
for (j=1;j<=n-(1<<i)+1;j++)
{
aux=1<<(i-1);
M[i][j]= min(M[i-1][j] , M[i-1][j+aux] );
}
lg[1]=0;
for (i=2;i<=n;i++)
lg[i]=lg[i/2]+1;
output=fopen("rmq.out","w");
for (i=1;i<=m;i++)
{
fscanf(input,"%ld %ld",&x,&y);
lung=y-x+1;//lungimea segmentului [x,y]
linie=lg[lung];//linia pe care se gaseste minimul intervalului
aux=lung-(1<<linie);//1<<linie=lungime de inceput a intervalelor ce se pot afla pe linia linie=cea mai mica putere a lui 2 mai mica decar lungimea intervalului
fprintf(output,"%ld\n",min(M[linie][x],M[linie][x+aux]));
}
fclose(input);
fclose(output);
return 0;
}