Overview

This problem asks us to count the number of contiguous flower intervals \([l, r]\) that simultaneously satisfy two conditions: “variety diversity (Condition 1)” and “height balance (Condition 2)”.

Since the data size is as large as \(N \le 2 \times 10^5\), checking every interval individually would result in a Time Limit Exceeded (TLE). However, by focusing on the “monotonicity” of the conditions, we can solve this efficiently by combining the “two-pointer technique (sliding window)” with “sliding minimum/maximum (deque-based technique)”.

---

Analysis

1. Discovering Monotonicity

The key insight of this problem is the following property (monotonicity): “When the right endpoint \(r\) is fixed, moving the left endpoint \(l\) to the right (shrinking the interval) makes both conditions easier to satisfy.”

• Condition 1 (Variety diversity): \(D \times (r - l + 1) \le K\) When the interval \([l, r]\) is shrunk, the interval length \((r - l + 1)\) decreases, and the number of distinct varieties \(D\) either decreases or stays the same. Therefore, the product always decreases or stays the same, making the condition easier to satisfy.
• Condition 2 (Height balance): \(\max - \min \le M\) When the interval \([l, r]\) is shrunk, the maximum value in the interval decreases (or stays the same) and the minimum value increases (or stays the same). Therefore, the difference \(\max - \min\) always decreases or stays the same, making the condition easier to satisfy.

2. Applying the Two-Pointer Technique

Consider moving the right endpoint \(r\) sequentially through \(1, 2, \ldots, N\). For each condition, we maintain the “minimum (leftmost) left endpoint” that satisfies it.

• Let \(l_1\) be the minimum left endpoint that satisfies Condition 1.
• Let \(l_2\) be the minimum left endpoint that satisfies Condition 2.

Due to monotonicity, when the right endpoint \(r\) advances to the right, the left endpoints \(l_1, l_2\) never move back to the left (they always move right or stay in place). Therefore, the range of left endpoints \(l\) that simultaneously satisfy both conditions is: $\(\max(l_1, l_2) \le l \le r\)$

Each time the right endpoint \(r\) advances by one, we move \(l_1\) and \(l_2\) to the right until the conditions are satisfied. If \(\max(l_1, l_2) \le r\), then the number of valid intervals with right endpoint \(r\) can be instantly computed as \(r - \max(l_1, l_2) + 1\).

---

Algorithm

Checking Condition 1 (Variety Diversity)

We record the occurrence count of each variety in the interval using an array (or hash map) and maintain the current number of unique varieties \(D\). * When the right endpoint \(r\) advances, we increment the occurrence count of the newly added variety. If it appears for the first time, we increase \(D\) by \(1\). * While \(D \times (r - l_1 + 1) > K\), we advance \(l_1\) to the right and decrement the occurrence count of the removed variety. If the occurrence count becomes \(0\), we decrease \(D\) by \(1\).

Checking Condition 2 (Height Balance)

To efficiently obtain the maximum and minimum values in the interval \([l_2, r]\), we use the sliding maximum/minimum algorithm (using std::deque). * Deque for maximum value management (max_dq): The deque is maintained so that values are in descending order (heights corresponding to indices are in decreasing order). * Deque for minimum value management (min_dq): The deque is maintained so that values are in ascending order (heights corresponding to indices are in increasing order). * When adding the right endpoint \(r\), we remove elements from the back of the deque that are “unnecessary as maximum” or “unnecessary as minimum” compared to \(B_r\), then add \(r\). * While the difference between the maximum value (front of max_dq) and the minimum value (front of min_dq) exceeds \(M\), we advance \(l_2\) to the right. * If, as a result of advancing \(l_2\), the index at the front of the deque becomes less than \(l_2\) (outside the interval), we remove it from the deque.

---

Complexity

• Time complexity: \(O(N)\) The right endpoint \(r\) advances from \(0\) to \(N-1\) one step at a time. Also, the left endpoints \(l_1, l_2\) each advance to the right at most \(N\) times. Each element is added to and removed from the deque at most once, so operations throughout the entire loop take constant time, resulting in an overall complexity of \(O(N)\).

• Space complexity: \(O(N)\) The array freq (size \(N+1\)) for recording variety occurrence counts, the deques, and the arrays holding input data use \(O(N)\) memory.

---

Implementation Notes

1. Fast I/O: In C++, since the input data size is as large as \(N = 2 \times 10^5\), we use cin.tie(NULL); ios_base::sync_with_stdio(false); to speed up input/output.

2. Preventing Overflow: The expression for Condition 1 checking, unique_count * (r - l1 + 1), can reach a maximum of \(2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}\), which overflows a 32-bit integer type. In C++, calculations must be performed using the long long type.

3. Index Management with Deque (std::deque): The deque stores indices rather than height values themselves. This allows us to easily determine and remove “elements that are to the left of the current left endpoint \(l_2\) (i.e., outside the interval)” using a check like max_dq.front() < l2.

   Source Code

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long K, M;
    if (!(cin >> N >> K >> M)) return 0;

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

    // 条件1用の変数（品種の多様さ）
    vector<int> freq(N + 1, 0);
    int unique_count = 0;
    int l1 = 0;

    // 条件2用の変数（高さのバランス）
    deque<int> max_dq, min_dq;
    int l2 = 0;

    long long ans = 0;

    for (int r = 0; r < N; ++r) {
        // 条件1の更新
        if (freq[A[r]] == 0) {
            unique_count++;
        }
        freq[A[r]]++;

        while ((long long)unique_count * (r - l1 + 1) > K) {
            freq[A[l1]]--;
            if (freq[A[l1]] == 0) {
                unique_count--;
            }
            l1++;
        }

        // 条件2の更新
        while (!max_dq.empty() && B[max_dq.back()] <= B[r]) {
            max_dq.pop_back();
        }
        max_dq.push_back(r);

        while (!min_dq.empty() && B[min_dq.back()] >= B[r]) {
            min_dq.pop_back();
        }
        min_dq.push_back(r);

        while (B[max_dq.front()] - B[min_dq.front()] > M) {
            l2++;
            if (max_dq.front() < l2) {
                max_dq.pop_front();
            }
            if (min_dq.front() < l2) {
                min_dq.pop_front();
            }
        }

        // 両方の条件を満たす l の最小値は max(l1, l2)
        int max_l = max(l1, l2);
        if (max_l <= r) {
            ans += (r - max_l + 1);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

This editorial was generated by gemini-3.5-flash-thinking.