Stock Trader S Alternating Streak You are a day tr...

Use dynamic programming with four states for every possible ending price:

• up0, down0: last move direction, mulligan unused.
• up1, down1: last move direction, mulligan already used.

Segment trees provide the best previous state among prices at least M lower or higher in O(log N) time.

cpp
#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
private:
    int size;
    vector<int> tree;

public:
    explicit SegmentTree(int n) {
        size = 1;
        while (size < n) size <<= 1;
        tree.assign(2 * size, 0);
    }

    void update(int position, int value) {
        position += size;
        tree[position] = max(tree[position], value);

        position >>= 1;
        while (position > 0) {
            tree[position] = max(tree[position << 1],
                                 tree[position << 1 | 1]);
            position >>= 1;
        }
    }

    int query(int left, int right) const {
        if (left > right) return 0;

        left += size;
        right += size;
        int result = 0;

        while (left <= right) {
            if (left & 1) result = max(result, tree[left++]);
            if (!(right & 1)) result = max(result, tree[right--]);

            left >>= 1;
            right >>= 1;
        }

        return result;
    }
};

long long solve(int N, int M, vector<int>& P) {
    if (N == 0) return 0;

    vector<long long> values(P.begin(), P.end());
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());

    int K = static_cast<int>(values.size());

    SegmentTree upWithoutMulligan(K);
    SegmentTree downWithoutMulligan(K);
    SegmentTree upWithMulligan(K);
    SegmentTree downWithMulligan(K);

    int answer = 1;

    // A direction must be strict. Thus, when M = 0, the actual
    // minimum difference between two integer prices is still 1.
    long long requiredDifference = max(1LL, static_cast<long long>(M));

    for (long long currentPrice : P) {
        int currentIndex = static_cast<int>(
            lower_bound(values.begin(), values.end(), currentPrice)
            - values.begin()
        );

        /*
         * For an up-step:
         * previousPrice <= currentPrice - requiredDifference
         */
        long long maximumLowerPrice =
            currentPrice - requiredDifference;

        int lowerEnd = static_cast<int>(
            upper_bound(values.begin(), values.end(), maximumLowerPrice)
            - values.begin()
        ) - 1;

        /*
         * For a down-step:
         * previousPrice >= currentPrice + requiredDifference
         */
        long long minimumHigherPrice =
            currentPrice + requiredDifference;

        int higherStart = static_cast<int>(
            lower_bound(values.begin(), values.end(), minimumHigherPrice)
            - values.begin()
        );

        // Alternating transition: down -> up, without using mulligan.
        int bestDown0OnLowerPrices =
            downWithoutMulligan.query(0, lowerEnd);

        int currentUp0 =
            bestDown0OnLowerPrices == 0
                ? 1
                : bestDown0OnLowerPrices + 1;

        /*
         * End with an up-step after the mulligan has been used:
         *
         * 1. downWithMulligan -> upWithMulligan
         *    Normal alternation; mulligan was used earlier.
         *
         * 2. upWithoutMulligan -> upWithMulligan
         *    Two consecutive up-steps; use the mulligan now.
         */
        int bestDown1OnLowerPrices =
            downWithMulligan.query(0, lowerEnd);

        int bestUp0OnLowerPrices =
            upWithoutMulligan.query(0, lowerEnd);

        int up1Previous =
            max(bestDown1OnLowerPrices, bestUp0OnLowerPrices);

        int currentUp1 =
            up1Previous == 0 ? 0 : up1Previous + 1;

        // Alternating transition: up -> down, without using mulligan.
        int bestUp0OnHigherPrices =
            upWithoutMulligan.query(higherStart, K - 1);

        int currentDown0 =
            bestUp0OnHigherPrices == 0
                ? 1
                : bestUp0OnHigherPrices + 1;

        /*
         * End with a down-step after the mulligan has been used:
         *
         * 1. upWithMulligan -> downWithMulligan
         * 2. downWithoutMulligan -> downWithMulligan
         */
        int bestUp1OnHigherPrices =
            upWithMulligan.query(higherStart, K - 1);

        int bestDown0OnHigherPrices =
            downWithoutMulligan.query(higherStart, K - 1);

        int down1Previous =
            max(bestUp1OnHigherPrices, bestDown0OnHigherPrices);

        int currentDown1 =
            down1Previous == 0 ? 0 : down1Previous + 1;

        /*
         * Update only after all queries, ensuring that the current
         * element cannot be used as its own predecessor.
         */
        upWithoutMulligan.update(currentIndex, currentUp0);
        downWithoutMulligan.update(currentIndex, currentDown0);

        if (currentUp1 > 0) {
            upWithMulligan.update(currentIndex, currentUp1);
        }

        if (currentDown1 > 0) {
            downWithMulligan.update(currentIndex, currentDown1);
        }

        answer = max({
            answer,
            currentUp0,
            currentDown0,
            currentUp1,
            currentDown1
        });
    }

    return answer;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    int M;

    cin >> N;
    cin >> M;

    vector<int> P(N);
    for (int i = 0; i < N; ++i) {
        cin >> P[i];
    }

    cout << solve(N, M, P) << '\n';
    return 0;
}

Complexity: O(N log N) time and O(N) memory.