Cod sursa(job #3203543)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 13 februarie 2024 20:58:01
Problema Range minimum query Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>

#define MAXN 100001
#define MAXK 1000001
#define MIN(a, b) ((a)>(b)?(b):(a))

using namespace std;

int st[30][MAXN];
int lg[MAXK];

int n, q;

int main(){

  for(int i=2; i<=MAXK; i++){
    lg[i] = 1 + lg[i/2];
  }

  FILE *fin, *fout;
  fin = fopen("rmq.in", "r");
  fscanf(fin, "%d%d", &n, &q);
  for(int i=0; i<n; i++){
    fscanf(fin, "%d", &st[0][i]);
  }

  for(int i=1; i<=lg[n]; i++){
    for(int j=0; j+(1<<(i-1))<n; j++){
      st[i][j] = MIN( st[i-1][j], st[i-1][j+(1<<(i-1))] );
      //printf("%d ", st[i][j]);
    }//printf("\n");
  }

  fout = fopen("rmq.out", "w");
  while(q>0){
    int i, j; fscanf(fin, "%d%d", &i, &j); i--; j--;
    if(i>j){int aux = i; i = j; j = aux;}
    int len = j-i+1;
    int k = lg[len];
    int m = MIN(st[k][i], st[k][j-(1<<k)+1]);
    fprintf(fout, "%d\n", m);
    q--;
  }

  fclose(fin);
  fclose(fout);
  return 0;
}