fork download
copy 
  1. program mountain;
  2. Uses sysutils, Math;
  3.  
  4. const
  5.     MAXN = 100005;
  6.  
  7. Type elenco= Array of LongInt;
  8.  
  9. var
  10.     ANS, N, i, id, x, maxMountainLength, len : LongInt;
  11.     P, leftLIS, rightLIS, index: Array[0..MAXN-1] of LongInt;
  12.     LIS : elenco;
  13.  
  14.  
  15.  
  16.  
  17. Procedure ricercaUpper (var w:elenco; target:Longint); (*ritorna indice del valore maggiore/uguale a target oppure -1 se non esiste*)
  18.   var m,start,eend: Longint;
  19.  
  20.  begin  
  21.    start:=0; eend:=len-1 ; m:=-1;
  22.    while start<=eend do
  23.            begin
  24.                   m:=(start + eend) div 2;
  25.                   if w[m]<target then  start:=m+1
  26.                                  else  if w[m]>=target then  begin id:=m;  eend:=m-1 end;
  27.            end;
  28.    if start=len then id:=-1;
  29.  
  30.  end;
  31.  
  32.  
  33.  
  34.  
  35. begin
  36.  
  37.  
  38.     ReadLn(N);
  39.  
  40.     for i:=0 to N-1 do begin Read(P[i]); index[i]:=-1; end;
  41.  
  42.     ReadLn();
  43.     ANS := 0; 
  44.     maxMountainLength := 0;
  45. 	(*leftLIS[i] stores the length of longest increasing subsequence ending at index i*)
  46. 	(*rightLIS[i] stores the length of longest decreasing subsequence starting at index i*)
  47.     len:=1; SetLength(LIS,len); LIS[0]:=P[0]; index[0]:=0;
  48.     for i:=0 to  N-1 do begin leftLIS[i]:=1; rightLIS[i]:=1; end;
  49.     (*Calculate LIS from left to right for each position*)
  50.     for i :=1 to N-1 do
  51.                     begin
  52.                            ricercaUpper(Lis, P[i]);
  53.                            // if element in not present in lis insert at the end
  54.  
  55.                            if id=-1 then
  56.                                    begin
  57.                                      len:=len+1;
  58.                                      SetLength(LIS,len);
  59.                                      LIS[len-1] := P[i];
  60.                                      index[len-1]:=i;
  61.                                      leftLIS[i]:=len;
  62.                                    end
  63.                                  else
  64.                                     begin
  65.                                       // if element is to be inserted in lis
  66.                                       if (id<>0) and ((P[index[id]]<P[index[id]-1]) and (P[index[id]]<P[index[id]+1])) then
  67.                                                      begin
  68.                                                         LIS[id] := P[i];
  69.                                                         leftLIS[i]:=id+1;                                                       
  70.                                                      end
  71.                                                else 
  72.                                                     leftLIS[i]:=0;
  73.  
  74.                                     end;                   
  75.                     end; 
  76.  
  77.        (* Calculate LIS from right to left (decreasing subsequence) for each position*)
  78.  
  79.    len:=1; SetLength(LIS,len); LIS[0]:=P[N-1]; index[0]:=N-1;
  80.  
  81.    for i :=N-2  downto 0 do
  82.                           begin                        
  83.                              ricercaUpper(Lis, P[i]);
  84.                              if id=-1 then
  85.                                    begin
  86.                                      len:=len+1;
  87.                                      SetLength(LIS,len);
  88.                                      LIS[len-1] := P[i];
  89.                                      index[len-1]:=i;
  90.                                      rightLIS[i]:=len;
  91.                                    end
  92.                                  else
  93.                                     begin
  94.                                       // if element is to be inserted in lis
  95.                                       if (id<>0) and ((P[index[id]]<P[index[id]-1]) and (P[index[id]]<P[index[id]+1])) then
  96.                                                      begin
  97.                                                         LIS[id] := P[i];
  98.                                                         rightLIS[i]:=id+1;                                                        
  99.                                                      end
  100.                                                 else  
  101.                                                    rightLIS[i]:=0;
  102.  
  103.  
  104.                                    end;                    
  105.                     end;
  106.      (* Find the maximum length of mountain subsequence*)
  107.     // for every index check for longest mountain array,
  108.     for i := 0 to N-1 do
  109.              begin
  110.                 if (leftLIS[i] >=1) AND (rightLIS[i] >= 1) then 
  111.                       begin
  112.                         x := leftLIS[i] + rightLIS[i] - 1;
  113.                         maxMountainLength := max(maxMountainLength, x);
  114.                       end;  
  115.              end;
  116.  
  117.     // returning removals
  118.  
  119.    ANS:= N - maxMountainLength; 
  120.    WriteLn(ANS);
  121. end.
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
6
2 3 0 5 1 4
stdout
copy 
2
https://ideone.com/WklSYQ
language:
Pascal (fpc 3.0.4)
created:
5 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!