Pagini recente » Borderou de evaluare (job #784353) | Cod sursa (job #2903843)
#include <fstream>
#define NMAX 100002
#define INF 0x3f3f3f3f
#pragma GCC optimize ("O3")
using namespace std;
ifstream fin("rmq.in");
ofstream fout("rmq.out");
long int aint[3 * NMAX], N, M, mx;
void update(long int n,long int left, long int right, long int poz, long int val)
{
if(left == right)
aint[n] = val;
else
{
long int m = (left + right) / 2;
if(poz <= m)
update(2 * n, left, m, poz, val);
else
update(2 * n + 1, m + 1, right, poz, val);
aint[n] = min(aint[2 * n], aint[2 * n + 1]);
}
}
void query( long int n, long int left, long int right, long int a,long int b)
{
if(a <= left && right <= b)
mx = min(mx, aint[n]);
else
{
long int m = (left + right) / 2;
if(a <= m)
query(2 * n, left, m, a, b);
if(b > m)
query(2 * n + 1, m + 1, right, a, b);
}
}
int main()
{
long int x, y, i;
fin>>N>>M;
for(i = 1; i <= N; ++i)
{
fin>>x;
update(1, 1, N, i, x);
}
for(i = 1; i <= M; ++i)
{
fin>>x>>y;
mx = INF;
query(1, 1, N, x, y);
fout<<mx<<"\n";
}
return 0;
}