Submission #1221349

---

Source Code Expand

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<cstdlib>
#include<ctime>
#include<climits>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define inf 0x3f3f3f3f
#define N 100010
#define M 
using namespace std;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int n,a[N],f[N][2];

int main(){
  n=read();
  rep(i,1,n) a[i]=read();
  f[1][0]=1;f[1][1]=1;
  rep(i,2,n){
    f[i][0]=f[i][1]=inf;
    if(a[i]>=a[i-1]){
      f[i][0]=min(f[i][0],f[i-1][0]);
      f[i][1]=min(f[i][1],min(f[i-1][0],f[i-1][1])+1);
    }
    if(a[i]<=a[i-1]){
      f[i][0]=min(f[i][0],min(f[i-1][0],f[i-1][1])+1);
      f[i][1]=min(f[i][1],f[i-1][1]);
    }
  }
  printf("%d\n",min(f[n][0],f[n][1]));
  return 0;
}

Submission Info

Judge Result