Cod sursa(job #308943)

Utilizator CosminCosmin Negruseri Cosmin Data 29 aprilie 2009 03:55:03
Problema Range minimum query Scor 80
Compilator fpc Status done
Runda Arhiva educationala Marime 0.83 kb
var  
    n, m, i, k, x, y, l : longint;  
    log : array[0..100000] of byte;  
    min : array[0..18,1..100000] of longint;  
    f, g: text;  
  
function minim (a, b : longint) : longint;  
begin  
if (a < b) then minim := a else  minim := b;  
end;  
  
begin  
assign  (f, 'rmq.in');      assign  (g, 'rmq.out');  
reset   (f);                rewrite (g);  
readln  (f, n, m);  
  
for i := 1 to n do readln (f, min[0, i]);  
  
for i := 2 to n do log[i] := log[i shr 1] + 1;  
  
for k := 1 to log[n] do  
    for i := 1 to n - (1 shl k) + 1 do  
        min [k, i] :=  minim (min[k-1, i], min[k-1, i + (1 shl (k-1))]);  
  
for i := 1 to m do  
    begin  
    readln  (f, x, y);  
    l := log[y - x + 1];  
    writeln (g, minim (min[l, x], min[l, y + 1 - (1 shl l)]));  
    end;      
close   (f);                close   (g);  
end.