Overview

The problem asks us to find the number of pairs of mountains of the same color such that all mountains between them are “less than or equal to at least one of the two endpoints.”

The seemingly complex condition of having a “clear view” can be rephrased using the positions of “the first higher mountain” to the left and right of each mountain. This allows us to solve the problem efficiently in \(O(N \log N)\) time using a monotonic stack and binary search.

---

Analysis

1. Naive Approach and Its Limitations

If we naively check whether \(H_k \leq \max(H_i, H_j)\) holds for all intermediate mountains \(k\) for every pair of mountains of the same color \((i, j)\) (\(i < j\)), it would take \(O(N^3)\) or \(O(N^2)\) time in the worst case. Under the constraint \(N \le 2 \times 10^5\), this will result in a Time Limit Exceeded (TLE).

We need to count the valid pairs more efficiently.

2. Rephrasing the Condition

Let us simplify the condition in the problem description: “\(H_k \leq \max(H_i, H_j)\) for all \(k\) (\(i < k < j\)).” Since all mountain heights are distinct (\(H_i \neq H_j\)), any pair \((i, j)\) can be completely partitioned into the following two cases:

Case 1: When \(H_i > H_j\)

In this case, \(\max(H_i, H_j) = H_i\). The condition becomes: “\(H_k < H_i\) for all \(k\) such that \(i < k < j\).”

This is equivalent to \(j < R_i\), where \(R_i\) is the index of the “first mountain to the right of mountain \(i\) that is higher than mountain \(i\).” Therefore, we only need to count the number of indices \(j\) that satisfy all of the following conditions: - \(i < j < R_i\) - \(C_i = C_j\)

Case 2: When \(H_i < H_j\)

In this case, \(\max(H_i, H_j) = H_j\). The condition becomes: “\(H_k < H_j\) for all \(k\) such that \(i < k < j\).”

This is equivalent to \(L_j < i\), where \(L_j\) is the index of the “first mountain to the left of mountain \(j\) that is higher than mountain \(j\).” Therefore, for each fixed \(j\), we only need to count the number of indices \(i\) that satisfy all of the following conditions: - \(L_j < i < j\) - \(C_i = C_j\)

Since these two cases are mutually exclusive (\(H_i > H_j\) and \(H_i < H_j\) cannot occur simultaneously), we can count the number of valid pairs for each case independently and sum them up. This covers all “clear view” pairs without any double-counting.

---

Algorithm

The program operates in the following three steps:

Step 1: Finding the First Higher Mountain to the Left and Right (Monotonic Stack)

For each mountain \(i\), we find the following values: - \(L_i\): The largest index \(k\) to the left of \(i\) (\(k < i\)) such that \(H_k > H_i\) (or \(-1\) if it does not exist) - \(R_i\): The smallest index \(k\) to the right of \(i\) (\(k > i\)) such that \(H_k > H_i\) (or \(N\) if it does not exist)

These can be computed in \(O(N)\) total time complexity using a technique called a Monotonic Stack.

Step 2: Creating Lists of Mountain Indices for Each Color

For each color \(c\), we create a list pos[c] containing the indices of the mountains of that color in ascending order. We also record idx_in_pos[i], which represents the 0-based index of mountain \(i\) within pos[C[i]].

Step 3: Fast Counting via Binary Search

For each mountain \(i\), we efficiently count the number of valid pairs with \(i\) as an endpoint using binary search (lower_bound / upper_bound).

• Counting for Case 1 (\(H_i > H_j\)): We find the number of elements in pos[C[i]] whose indices are strictly greater than \(i\) and strictly less than \(R_i\). This can be computed in \(O(\log N)\) time by using binary search to find the position of the first element in pos[C[i]] that is \(\ge R_i\), and then subtracting the number of elements \(\le i\) (which is idx_in_pos[i] + 1).

• Counting for Case 2 (\(H_i < H_j\)): We fix mountain \(j\) (referred to as the loop variable i in the code) and find the number of elements in pos[C[j]] whose indices are strictly greater than \(L_j\) and strictly less than \(j\). This can be computed in \(O(\log N)\) time by using binary search to find the position of the first element in pos[C[j]] that is \(> L_j\), and then subtracting this position from \(j\)’s position (idx_in_pos[j]).

---

Complexity

• Time Complexity: \(O(N \log N)\)

  • Computing \(L_i\) and \(R_i\) takes \(O(N)\) time.
  • Constructing the index lists for each color takes \(O(N)\) time.
  • For each mountain \(i\), we perform binary searches twice. Since we do this for all \(N\) elements, the counting step takes \(O(N \log N)\) time.
  • Therefore, the overall time complexity is \(O(N \log N)\), which is well within the execution time limit.

• Space Complexity: \(O(N)\)

  • The arrays L, R, pos, idx_in_pos, and the stack st all have a maximum size of \(N\) (or \(N+1\)), so the space complexity is \(O(N)\).

---

Implementation Details

• Behavior of the Monotonic Stack: By scanning from left to right and removing (popping) all mountains in the stack that are lower than the currently considered mountain, the top of the stack will always contain the closest mountain to the left that is higher than the current one. Similarly, scanning from right to left allows us to compute \(R_i\).

• Boundary Values for Binary Search: To simplify boundary condition handling, we use sentinels: we set \(L_i\) to \(-1\) and \(R_i\) to \(N\) when they do not exist.

  Source Code

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

using namespace std;

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

    int N;
    if (!(cin >> N)) return 0;

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

    // L[i]: i より左側で H[i] より高い最初の要素のインデックス
    // R[i]: i より右側で H[i] より高い最初の要素のインデックス
    vector<int> L(N, -1), R(N, N);
    vector<int> st;
    for (int i = 0; i < N; ++i) {
        while (!st.empty() && H[st.back()] < H[i]) {
            st.pop_back();
        }
        if (!st.empty()) L[i] = st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = N - 1; i >= 0; --i) {
        while (!st.empty() && H[st.back()] < H[i]) {
            st.pop_back();
        }
        if (!st.empty()) R[i] = st.back();
        st.push_back(i);
    }

    // 各色ごとのインデックスのリスト
    vector<vector<int>> pos(N + 1);
    // idx_in_pos[i]: pos[C[i]] における要素 i のインデックス
    vector<int> idx_in_pos(N);
    for (int i = 0; i < N; ++i) {
        idx_in_pos[i] = pos[C[i]].size();
        pos[C[i]].push_back(i);
    }

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        // Case 1: H_i > H_j (i < j < R_i かつ C_i = C_j)
        {
            int limit_r = R[i];
            auto it = lower_bound(pos[C[i]].begin(), pos[C[i]].end(), limit_r);
            int idx_limit = distance(pos[C[i]].begin(), it);
            int idx_cur = idx_in_pos[i];
            if (idx_limit > idx_cur + 1) {
                ans += (idx_limit - (idx_cur + 1));
            }
        }
        // Case 2: H_i < H_j (L_j < i < j かつ C_i = C_j)
        // ここでは j をループの変数 i とみなして計算する
        {
            int limit_l = L[i];
            auto it = upper_bound(pos[C[i]].begin(), pos[C[i]].end(), limit_l);
            int idx_limit = distance(pos[C[i]].begin(), it);
            int idx_cur = idx_in_pos[i];
            if (idx_cur > idx_limit) {
                ans += (idx_cur - idx_limit);
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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