Cod sursa(job #9671)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 27 ianuarie 2007 16:36:33
Problema Secventa 5 Scor 0
Compilator fpc Status done
Runda Unirea 2007, clasele 11-12 Marime 1.93 kb

 const
     FIN = 'secv5.in';
     FOUT = 'secv5.out';
     NMAX = 1 shl 20;

  var T, V, IND : array[ 1..NMAX ] of longint;
      SEL : array[ 0..NMAX ] of integer;
      N, L, U, K, ans : longint;
      f, g : text;


 procedure read_Data;
  var i : longint;
   begin
    assign( f, FIN ); reset( f );
    readln( f, n, l, u );
    for i := 1 to n do readln( f, v[i] );
    for i := 1 to n do ind[i] := i;
    close( f );
   end;

 procedure poz( lo, hi : longint );
  var i, j, di, dj, aux : longint;
   begin
    i := lo; j := hi; di := 0; dj := - 1;
      while i < j do
        begin
         if V[ind[i]] > V[ ind[j] ] then begin aux := ind[i]; ind[i] := ind[j]; ind[j]:=aux;
                                               aux := di; di := - dj; dj := - aux;
                                         end;
         inc( i, di );
         inc( j, dj );
      end;
    k := i;
  end;

 procedure  quick( lo, hi : longint );
  begin
   if lo < hi then
     begin
       poz( lo, hi );
       quick( lo, k - 1 );
       quick( k + 1, hi );
     end;
 end;

 procedure normalizare;
  var i, k : longint;
  begin
    k := 1;
    T[ind[1]] := 1;
    for i := 2 to n do
      begin
        if V[ind[i]] <> V[ ind[i-1] ] then inc(k);
        T[ind[i]] := k;
      end;
 end;

 procedure solve;
  var i, s, j, p : longint;
   begin
    for i := 1 to n do
      begin
       s := 0;
       p := 1;
        for j := i downto 1 do
          begin
            if sel[T[j]] = 0 then begin sel[T[j]] := 1; inc( s ); end;
            if ( s >= l ) and ( s <= u ) then inc(ans);
            if s > u then begin p:=i; break; end;
           end;
          for j := i downto 1 do sel[T[j]] := 0;
      end;
   end;

 procedure save;
  begin
   assign( g, FOUT ); rewrite( g );
   writeln( g, ans );
   close( g );
  end;


 begin
  read_data;
  quick( 1, n );
  normalizare;
  solve;
  save;
 end.