Pagini recente » Rezultatele filtrării | Cod sursa (job #2967565) | Cod sursa (job #309134) | Cod sursa (job #391309) | Cod sursa (job #833647)
Cod sursa(job #833647)
#include <fstream>
#define MAX_SIZE 100000
using namespace std;
int matrix[18][MAX_SIZE];
int lg[MAX_SIZE];
int minim(int a , int b)
{
if (a < b) return a;
else return b;
}
int main()
{
ifstream input("rmq.in");
ofstream output("rmq.out");
int N , M;
input >> N >> M;
int logN = 1;
while ( (1 << logN) < N)
{
logN ++;
}
logN --;
lg[1] = 0;
for (int i = 2 ; i <= N;i++)
{
lg[ i ] = lg[i/2] + 1;
}
for (int i = 1;i <= N;i++)
{
input >> matrix[0][i];
}
for (int i = 1 ; i <= logN;i++)
for (int j = 1;j<=N - ( 1 << i) + 1;j++)
{
matrix[i][j] = minim(matrix[i-1][j] , matrix[i-1][j+(1 << (i-1))]);
}
for (int i = 0 ; i< M;i++)
{
int x , y;
input >> x >> y;
int t = y - x + 1;
int l = lg[t];
t = t - ( 1 << l);
output << minim( matrix[l][x] , matrix[l][x+t]) << "\n";
}
input.close();
output.close();
return 0;
}