Submission #1221351

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cassert>
 
using namespace std;
 
#define sz(x) (int)(x.size())
#define fi(a, b) for(int i=a;i<b;++i)
#define fj(a, b) for(int j=a;j<b;++j)
#define fk(a, b) for(int k=a;k<b;++k)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
////////////////

int const N = 1e5 + 41;
int const INF = 1e9 + 41;

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

void solve(){
	cin  >> n;
	fi(1, n+1){
		cin >> a[i];
	}
	fi(0, N) fj(0, 2) d[i][j] = INF;
	d[1][0] = d[1][1] = 1;
	fi(2, n+1){
		d[i][0] = d[i][1] = (1 + min(d[i-1][0], d[i-1][1]));
		if(a[i-1] <= a[i]) d[i][1] = min(d[i-1][1], d[i][1]);
		if(a[i-1] >= a[i]) d[i][0] = min(d[i-1][0], d[i][0]);
	}
	
	int ans = min(d[n][1], d[n][0]);
	cout << ans << endl;
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();

	return 0;
}

Submission Info

Judge Result