Language: C++

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
#include <string.h>

using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define all(s) s.begin(), s.end()

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> triple;
typedef double D;

int gcd(int a, int b) {
  if (a < b) { swap(a, b); }
  if (b == 0) { return a; }
  return gcd(b, a % b);
}

bool prime(int n) {
  for (int i = 2; i <= sqrt(n); ++i) {
    if (n % i == 0) { return false; }
  }
  return n != 1;
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INF = 1e9;
const ll MOD = 1000000007;  // 1e9 + 7

ll powmod(ll x, ll n) { // like pow(x, n)
  ll r = 1;
  while (n) {
    if (n & 1) {
      r = r * x % MOD;
    }
    x = x * x % MOD;
    n >>= 1;
  }
  return r;
}

const int COM_MAX = 500010;
ll fac[COM_MAX], facinv[COM_MAX], inv[COM_MAX];
void COMinit() {
  fac[0] = fac[1] = 1;
  facinv[0] = facinv[1] = 1;
  inv[1] = 1;
  for(int i = 2; i < COM_MAX; ++i) {
    fac[i] = fac[i-1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    facinv[i] = facinv[i-1] * inv[i] % MOD;
  }
}

ll COM(ll n, ll k) {
  return (fac[n] * facinv[k] % MOD) * facinv[n-k] % MOD;
}

ll PERM(ll n, ll k) {
  return (fac[n] * facinv[k] % MOD);
}

// A utility function to get the
// middle index of given range.
int getMid(int s, int e)
{
    return s + (e - s) / 2;
}

/*  A recursive function to get the sum of
    values in given range of the array.
    The following are parameters for this
    function.

    st       -> Pointer to segment tree
    node     -> Index of current node in
                the segment tree .
    ss & se  -> Starting and ending indexes
                of the segment represented
                by current node, i.e., st[node]
    l & r    -> Starting and ending indexes
                of range query */
int MaxUtil(int* st, int ss, int se, int l,
            int r, int node)
{
    // If segment of this node is completely
    // part of given range, then return
    // the max of segment
    if (l <= ss && r >= se)
        return st[node];

    // If segment of this node does not
    // belong to given range
    if (se < l || ss > r)
        return -1;

    // If segment of this node is partially
    // the part of given range
    int mid = getMid(ss, se);

    return max(MaxUtil(st, ss, mid, l, r,
                       2 * node + 1),
               MaxUtil(st, mid + 1, se, l,
                       r, 2 * node + 2));
}

/* A recursive function to update the nodes which
   have the given index in their range. The following
   are parameters st, ss and se are same as defined
   above index -> index of the element to be updated.*/
void updateValue(int arr[], int* st, int ss, int se,
                 int index, int value, int node)
{
    if (index < ss || index > se)
    {
        cout << "Invalid Input" << endl;
        return;
    }

    if (ss == se)
    {
        // update value in array and in segment tree
        arr[index] = value;
        st[node] = value;
    }
    else {
            int mid = getMid(ss, se);

            if (index >= ss && index <= mid)
                updateValue(arr, st, ss, mid, index,
                            value, 2 * node + 1);
            else
                updateValue(arr, st, mid + 1, se,
                            index, value, 2 * node + 2);

            st[node] = max(st[2 * node + 1],
                       st[2 * node + 2]);
    }
    return;
}

// Return max of elements in range from
// index l (query start) to r (query end).
int getMax(int* st, int n, int l, int r)
{
    // Check for erroneous input values
    if (l < 0 || r > n - 1 || l > r)
    {
        printf("Invalid Input");
        return -1;
    }

    return MaxUtil(st, 0, n - 1, l, r, 0);
}

// A recursive function that constructs Segment
// Tree for array[ss..se]. si is index of
// current node in segment tree st
int constructSTUtil(int arr[], int ss, int se,
                    int* st, int si)
{
    // If there is one element in array, store
    // it in current node of segment tree and return
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }

    // If there are more than one elements, then
    // recur for left and right subtrees and
    // store the max of values in this node
    int mid = getMid(ss, se);

    st[si] = max(constructSTUtil(arr, ss, mid, st,
                                 si * 2 + 1),
                 constructSTUtil(arr, mid + 1, se,
                                 st, si * 2 + 2));

    return st[si];
}

/* Function to construct segment tree from given array.
   This function allocates memory for segment tree.*/
int* constructST(int arr[], int n)
{
    // Height of segment tree
    int x = (int)(ceil(log2(n)));

    // Maximum size of segment tree
    int max_size = 2 * (int)pow(2, x) - 1;

    // Allocate memory
    int* st = new int[max_size];

    // Fill the allocated memory st
    constructSTUtil(arr, 0, n - 1, st, 0);

    // Return the constructed segment tree
    return st;
}

// A utility function to get minimum of two numbers
int minVal(int x, int y) { return (x < y)? x: y; }

// A utility function to get the
// middle index from corner indexes.
int getMidForMin(int s, int e) { return s + (e -s)/2; }

/* A recursive function to get the
minimum value in a given range
of array indexes. The following
are parameters for this function.

    st --> Pointer to segment tree
    index --> Index of current node in the
           segment tree. Initially 0 is
           passed as root is always at index 0
    ss & se --> Starting and ending indexes
                of the segment represented
                by current node, i.e., st[index]
    qs & qe --> Starting and ending indexes of query range */
int RMQUtil(int *st, int ss, int se, int qs, int qe, int index)
{
    // If segment of this node is a part
    // of given range, then return
    // the min of the segment
    if (qs <= ss && qe >= se)
        return st[index];

    // If segment of this node
    // is outside the given range
    if (se < qs || ss > qe)
        return INT_MAX;

    // If a part of this segment
    // overlaps with the given range
    int mid = getMidForMin(ss, se);
    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1),
                RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
}

// Return minimum of elements in range
// from index qs (quey start) to
// qe (query end). It mainly uses RMQUtil()
int getMin(int *st, int n, int qs, int qe)
{
    // Check for erroneous input values
    if (qs < 0 || qe > n-1 || qs > qe)
    {
        cout<<"Invalid Input";
        return -1;
    }

    return RMQUtil(st, 0, n-1, qs, qe, 0);
}

// A recursive function that constructs
// Segment Tree for array[ss..se].
// si is index of current node in segment tree st
int constructSTForMinUtilForMin(int arr[], int ss, int se,
                                int *st, int si)
{
    // If there is one element in array,
    // store it in current node of
    // segment tree and return
    if (ss == se)
    {
        st[si] = arr[ss];
        return arr[ss];
    }

    // If there are more than one elements,
    // then recur for left and right subtrees
    // and store the minimum of two values in this node
    int mid = getMidForMin(ss, se);
    st[si] = minVal(constructSTForMinUtilForMin(arr, ss, mid, st, si*2+1),
                    constructSTForMinUtilForMin(arr, mid+1, se, st, si*2+2));
    return st[si];
}

/* Function to construct segment tree
from given array. This function allocates
memory for segment tree and calls constructSTForMinUtilForMin() to
fill the allocated memory */
int *constructSTForMin(int arr[], int n)
{
    // Allocate memory for segment tree

    //Height of segment tree
    int x = (int)(ceil(log2(n)));

    // Maximum size of segment tree
    int max_size = 2*(int)pow(2, x) - 1;

    int *st = new int[max_size];

    // Fill the allocated memory st
    constructSTForMinUtilForMin(arr, 0, n-1, st, 0);

    // Return the constructed segment tree
    return st;
}


int main(int argc, char** argv) {
  int N, K;
  cin >> N >> K;
  vector<int> P(N);
  rep(i, N) {
    cin >> P[i];
  }


  int arr[200010];
  memset(arr, 0, sizeof(arr));
  rep(i, N) {
    arr[i] = P[i];
  }

  // Build segment tree from given array for max
  int* st_max = constructST(arr, N);
  // cout << getMax(st_max, N, 0, 2) << endl;

  // Build segment tree from given array for min
  int* st_min = constructSTForMin(arr, N);
  // cout << getMin(st_min, N, 0, 2) << endl;

  int same_count = 0;
  for(int i = 1; i + K - 2 < N - 1; ++i) {
    // For Debug
    // cout << i << "-" << i + K - 2 << endl ;
    // cout << "max:" << getMax(st_max, N, i, i + K - 2) << endl;
    // cout << "min:" << getMin(st_max, N, i, i + K - 2) << endl;
    int max_x = getMax(st_max, N, i, i + K - 2);
    int min_x = getMin(st_max, N, i, i + K - 2);
    int left  = P[i-1];
    int right = P[i + K - 1];
    if ((left < min_x) && (right > max_x)) {
      // For Debug
      // cout << i << "-" << i + K - 2 << endl ;
      // cout << "same" << endl;
      ++same_count;
    } else {
      // For Debug
      // cout << i << "-" << i + K - 2 << endl ;
      // cout << "not same" << endl;
    }
  }

  int increasing_count = 1;
  vector<int> max_increased(N);
  int unchanged_count = 0; // If this is larger than 2, then it should be decreased
  for (int i = 1; i < N; ++i) {
    if (P[i-1] < P[i]) {
      ++increasing_count;
      max_increased[i] = increasing_count;
      if (max_increased[i] >= K) {
        ++unchanged_count;
      }
    } else {
      increasing_count = 1;
      max_increased[i] = increasing_count;
    }
  }

  // For Debug
  // cout << "max_increased:" << endl;
  // for(int i = 1; i < N; ++i) {
  //   cout << max_increased[i] << " ";
  // }
  // cout << endl;
  // cout << "unchanged_count:" << unchanged_count << endl;

  cout << (N - K + 1) - same_count - max(unchanged_count - 1, 0) << endl;
}


Compiler output:
a.cc: In function 'int RMQUtil(int*, int, int, int, int, int)':
a.cc:251:16: error: 'INT_MAX' was not declared in this scope
  251 |         return INT_MAX;
      |                ^~~~~~~
a.cc:11:1: note: 'INT_MAX' is defined in header '<climits>'; this is probably fixable by adding '#include <climits>'
   10 | #include <string.h>
  +++ |+#include <climits>
   11 |