Advertisement
STANAANDREY

subseg fn

Jun 16th, 2021
1,044
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.71 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //----------------------------------
  4. constexpr int NMAX = 1e5 + 3;
  5. int f[NMAX];
  6. int dp[NMAX];
  7.  
  8. signed main() {
  9.     int a, b;
  10.     cin >> a >> b;
  11.     int n = 0;
  12.     for (int x, i = 0; i < b - a + 1; i++) {
  13.         cin >> x;
  14.         if (x != f[n]) {
  15.             f[++n] = x;
  16.         }
  17.     }
  18.     dp[1] = dp[2] = 1;
  19.     for (int i = 3; i <= n; i++) {
  20.         bool mono = false;
  21.         mono |= f[i] > f[i - 1] && f[i - 1] > f[i - 2];
  22.         mono |= f[i] < f[i - 1] && f[i - 1] < f[i - 2];
  23.         if (mono) {
  24.             dp[i] = dp[i - 1];
  25.         } else {
  26.             dp[i] = dp[i - 1] + 1;
  27.         }
  28.     }
  29.     cout << dp[n] << endl;
  30.     return 0;
  31. }
  32.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement