Cod sursa(job #2748668)

Utilizator bangaloredelfin bangalore Data 2 mai 2021 13:06:07
Problema Range minimum query Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.59 kb
#include <fstream>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN=100001,Log2Max=17;
int v[MaxN],mn[Log2Max][MaxN],lg2[MaxN];
int main() { 
  ifstream fin("rmq.in");
  ofstream fout("rmq.out");
  int n,q,x,y,lg;
  fin>>n>>q;
  for(int i=1;i<=n;i+=1)
	fin>>v[i];
  for(int i=3;i<=n;i+=1)
	lg2[i]=lg2[i>>1]+1;
  for(int i=1;i<=n;i+=1)
    mn[0][i]=v[i];
  for(int p=1;p<=Log2Max;p+=1)
	for(int i=1;i<=n;i+=1)
	  mn[p][i]=min(mn[p-1][i],mn[p-1][i+(1<<(p-1))]); 
  while(q--) {
	fin>>x>>y;
	lg=lg2[y-x+1];
    fout<<min(mn[lg][x],mn[lg][y-(1<<lg)+1])<<"\n";
  }
  return 0;
}