Get rid of consecutive duplicates which are nasty and note that the intervals do not share common point.
dp is not needed.

I've solved this problem finally, of course, but I still suppose its definition to be unclear a bit :) So some tests for you:

1 3
1 1 1

1

//

1 5
1 2 3 4 5

//

1 5
5 4 3 3 3

1

//

1 7
1 2 2 3 3 4 5

1

//

1 5
1 2 3 2 1

2

//

1 6
1 2 3 2 3 4

2 - that's the point!

//

1 6
3 2 1 4 4 5

2

//

1 6
1 2 1 2 1 2

3

//

1 6
1 2 3 1 2 1

3

hi, this is O(1) complexity problem, you might want to decrease the Difficulty i guess

to others: if you have found an extremum skip next point

Why WA 28?I don't understand.
Here is my code:
program gjkh;
var a,b,ch,n,i,kol,sh,fir,sec,thi:longint;
m:array[1..100001]of longint;
flag:boolean;
begin
read(a);readln(b);
n:=0;
while not seekeof do begin
read(ch);
  if (n=0)or(m[n]<>ch)then begin
  n:=n+1;
  m[n]:=ch;
  end;
end;
flag:=true;
kol:=1;
for i:=1 to n do begin
if (i=1)then fir:=m[i]
  else begin
    if (flag=true)then begin
    sec:=m[i];
    flag:=false;
    end
    else begin
    thi:=m[i];
      if ((thi-sec)*(sec-fir)>0)then begin
      fir:=sec;sec:=thi;
      end
      else begin
      fir:=thi;
      kol:=kol+1;
      flag:=true;
      end;
    end;
  end;
end;
writeln(kol);
end.

It can help you:
Test:
1 13
0 -10 -7 -10 1 -5 6 -10 -8 -8 -7 -10 1
Answer: 6

Edited by author 04.04.2018 15:40

does anybody have idea what it can be?

Remove repetitions before applying your algo i.e.: sequences like 2 1 2 2 2 2 1 change into 2 1 2 1
It helped me with WA#21

I resolved WA21 using this case:

1 5
1 1 2 3 4

Correct Answer => 1

the problem with my solution was initialisation of the slope in case the first 2 elements are equal.

1 5
3 2 1 1 2

could you give me some tricky tests please? i tried everything that came through my mind. Thanks.

try
1 3
-80000 0 80000

the turning point should be left to LAST group.

I don't know how to solve this problem with DP, because here is just a one cycle without any
cool thinking)
Where is a DP here?)

Function is not (strictly) increasing or decreasing, it is NON-DECREASING or NON-INCREASING.

Test:
1 6
1 1 2 2 3 3
Answer:
1, not 4!

input:
-3 3
2 2 1 2 2 1
output:
2

What I must print if

sample input
1 5
1 2 3 4 5

Input for this problem, as well as the sample input, contains \xE2\x80\x93 UTF-8 sequence at the beginning of negative numbers, doesn't it?

Edited by author 04.08.2005 17:33

could anyone help me with test number 5 or give some tests for which my solution gives wrong answer? I have checked all the tests from the webboard.

who can tell me what is the test #2?

Here is my code :
Const         tfi         =      '';
              tfo         =      '';
              max         =      10000 + 1;


Type          arr1I       =      array [0..max] of integer        ;


Var           f           :      arr1I                  ;
              a,b         :      integer                ;
              res         :      integer                ;
              fi,fo       :      text                   ;



Procedure Readfile;
Var     i : integer ;
Begin
     Assign(fi,tfi);
     Reset(fi);
     Readln(fi,a,b);
     For i := a to b do read(fi,f[i]);
     Close(fi);
End;

{--------------------------------------------------------------------}

Procedure Process;
Var     i,x,j : integer ;
Begin
     res := 1;
     If b - a = 1 then exit;
     res := 0;
     i := a;
     Repeat
           Inc(res);
           If f[i] <= f[i + 1] then
           Begin
                x := f[i + 1];
                j := i + 1;
                Repeat
                      If x <= f[j + 1] then
                      Begin
                           x := f[j + 1];
                           Inc(j);
                      End
                      Else break;
                      If j = b then exit;
                Until false;
                i := j + 1;
           End
           Else
           Begin
                x := f[i + 1];
                j := i + 1;
                Repeat
                      If x >= f[j + 1] then
                      Begin
                           x := f[j + 1];
                           Inc(j);
                      End
                      Else break;
                      If j = b then exit;
                Until false;
                i := j + 1;
           End;
           If i = b then
           Begin
                Inc(res);
                break;
           End;
     Until i > b;
End;

{--------------------------------------------------------------------}

Procedure Writefile;
Begin
     Assign(fo,tfo);
     Rewrite(fo);
     Writeln(fo,res);
     Close(fo);
End;

{--------------------------------------------------------------------}

Begin
     Readfile;
     Process;
     Writefile;
End.


Edited by author 21.12.2005 09:16