Cod sursa(job #166117)

Utilizator gurneySachelarie Bogdan gurney Data 27 martie 2008 14:22:26
Problema Range minimum query Scor 70
Compilator fpc Status done
Runda Arhiva educationala Marime 1.01 kb
program rmq;
  const
    fin='rmq.in';
    fout='rmq.out';
    nmax=100000;
var
  a:array[1..nmax] of longint;
  i,j,l,maxlog,n,m,x,y:longint;
  log:array[0..18] of longint;
  min:array[1..nmax,0..18] of longint;

function minim(x,y:longint):longint;
  begin
    if x<y then
      minim:=x
    else
      minim:=y;
  end;

begin
  assign(input,fin);
  assign(output,fout);
    rewrite(output);
    reset(input);
    readln(n,m);
    log[0]:=1;
    for i:=1 to 18 do
      log[i]:=log[i-1]*2;
    for i:=1 to n do
      readln(a[i]);
    maxlog:=trunc(ln(n)/ln(2));
    for i:=1 to n do
      min[i,0]:=a[i];
    for j:=1 to maxlog do
      for i:=1 to n-log[j]+1 do
        if min[i,j-1]<min[i+(log[j-1]),j-1] then
          min[i,j]:=min[i,j-1]
        else
          min[i,j]:=min[i+(log[j-1]),j-1];
    for i:=1 to m do
      begin
        readln(x,y);
        l:=trunc(ln(y-x+1)/ln(2));
        writeln(minim(min[x,l],min[y-log[l]+1,l]));
      end;
  close(output);
  close(input);
end.