#1084052 (C++17) No.2036 Max Middle

• 問題: No.2036 Max Middle
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:16:29
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,696 bytes
• コンパイル時間: 1,005 ms
• コンパイル使用メモリ: 91,008 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2025-05-14 13:17:50
• 合計ジャッジ時間: 5,393 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 4 TLE * 1 -- * 12

ソースコード

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

// Use long long for array values because the operation can decrease values potentially below the standard int range.
typedef long long ll;

// Global vector A to store the sequence, and N for its size.
vector<ll> A;
int N;
// A set to keep track of the indices k where A[k] is currently a peak.
// Using a set allows efficient checking of existence, insertion, and deletion (O(log N)).
set<int> peak_indices; 
// A queue to manage the indices of peaks that need to be processed.
// Using a queue implements a breadth-first like processing order of peaks.
queue<int> worklist;  

// Function to check if the element A[k] is a peak.
// According to the problem, A[k] is a peak if k is between 1 and N-2 (inclusive, using 0-based indexing for A)
// and satisfies the condition A[k-1] < A[k] and A[k] > A[k+1].
// Note: The problem statement uses 1-based indexing and defines the operation for index `i` where 1 <= i <= N-2.
// This corresponds to checking the triplet (A_i, A_{i+1}, A_{i+2}). In 0-based indexing, this triplet is (A[i-1], A[i], A[i+1]).
// The peak condition is A[i-1] < A[i] and A[i] > A[i+1].
// The element modified is A[i]. Let's denote the index `i` (from problem statement) as `k` in our code.
// So `k` represents the index of the element being modified/checked if it's a peak. Valid range for k is [1, N-2].
bool is_peak(int k) {
    // Check if index k is within the valid range for a peak [1, N-2].
    if (k < 1 || k > N - 2) { 
        return false;
    }
    // Check the peak condition: the element A[k] must be strictly greater than its left neighbor A[k-1]
    // and strictly greater than its right neighbor A[k+1].
    return A[k-1] < A[k] && A[k] > A[k+1];
}

// Function to update the status of a potential peak at index k.
// If k becomes a peak and wasn't tracked, add it to the set and worklist.
// If k ceases to be a peak and was tracked, remove it from the set.
void update_peak_status(int k) {
    // Check if index k is within the valid range [1, N-2]. Indices outside this range cannot be peaks.
    if (k < 1 || k > N - 2) {
        return;
    }
    
    // Determine if A[k] is currently a peak based on current values of A.
    bool current_is_peak = is_peak(k);
    // Check if index k is currently present in our set of peak indices.
    bool is_in_set = peak_indices.count(k);

    // Case 1: A[k] is currently a peak, but k is not in our set.
    // This means k has just become a peak (or was missed initially).
    if (current_is_peak && !is_in_set) {
        peak_indices.insert(k); // Add k to the set of peak indices.
        worklist.push(k);       // Add k to the worklist queue to be processed later.
    } 
    // Case 2: A[k] is not currently a peak, but k is in our set.
    // This means k used to be a peak but isn't anymore due to changes in neighbors.
    else if (!current_is_peak && is_in_set) {
        peak_indices.erase(k); // Remove k from the set of peak indices.
        // Note: k might still be present in the worklist queue. If it gets popped later,
        // the check `if (peak_indices.count(k) == 0)` will correctly skip it.
    }
    // Other cases:
    // - If current_is_peak is true and is_in_set is true, k is already a known peak. No action needed.
    // - If current_is_peak is false and is_in_set is false, k is not a peak and not tracked. No action needed.
}


int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read the size of the sequence N.
    cin >> N;
    // Resize the vector A to hold N elements.
    A.resize(N);
    // Read the N integer elements into vector A.
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // Initialize the process by finding all initial peaks.
    // Iterate through all possible indices k that can be a peak (1 to N-2).
    for (int k = 1; k <= N - 2; ++k) {
        if (is_peak(k)) { // If A[k] satisfies the peak condition
            peak_indices.insert(k); // Add its index k to the set of peaks.
            worklist.push(k);       // Add its index k to the initial worklist queue.
        }
    }

    // Variable to keep track of the total number of operations performed.
    ll total_ops = 0;

    // Main loop: Process peaks from the worklist as long as it's not empty.
    while (!worklist.empty()) {
        int k = worklist.front(); // Get the index of the peak element A[k] from the front of the queue.
        worklist.pop();           // Remove this index from the queue.

        // Check if the index k is still present in the set of active peaks.
        // It might have been removed if it ceased to be a peak due to a previous operation on a neighbor.
        // If it's not in the set, skip processing it.
        if (peak_indices.count(k) == 0) {
            continue;
        }
        
        // If k is in the set, it's a valid peak to operate on.
        // Remove k from the set because we are about to perform the operation, which destroys this peak.
        peak_indices.erase(k); 

        // Perform the operation as described in the problem:
        // Replace A[k] with min(A[k-1], A[k+1]) - 1.
        ll val_left = A[k-1];   // Value of the left neighbor.
        ll val_right = A[k+1]; // Value of the right neighbor.
        // The new value for A[k] is one less than the minimum of its neighbors.
        A[k] = min(val_left, val_right) - 1; 
        total_ops++; // Increment the total operations counter.

        // After modifying A[k], the peak conditions for indices k-1, k, and k+1 might have changed.
        // We need to re-evaluate these indices and update their status in the peak set and worklist.
        // `update_peak_status` function handles boundaries and updates correctly.
        update_peak_status(k - 1); // Check and update status for the element to the left of the original peak's left neighbor. Its peak condition depends on A[k-1]. The triplet is (A[k-2], A[k-1], A[k]). A[k] changed value.
        update_peak_status(k);     // Check and update status for index k itself. After the operation, A[k] is guaranteed not to be a peak because A[k] < A[k-1] and A[k] < A[k+1]. This call ensures it's removed from the set if somehow it was still there.
        update_peak_status(k + 1); // Check and update status for the element to the right of the original peak. Its peak condition depends on A[k]. The triplet is (A[k], A[k+1], A[k+2]). A[k] changed value.
    }

    // After the loop finishes (no more peaks can be processed), output the total count of operations.
    cout << total_ops << endl;

    return 0;
}