結果

問題 No.2036 Max Middle
ユーザー qwewe
提出日時 2025-05-14 13:06:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,323 bytes
コンパイル時間 829 ms
コンパイル使用メモリ 86,576 KB
実行使用メモリ 7,840 KB
最終ジャッジ日時 2025-05-14 13:07:46
合計ジャッジ時間 5,304 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 1 -- * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <vector> // Ensure vector is included

using namespace std;

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

    int N; // Length of the sequence
    cin >> N;

    // Use vector<long long> to store the sequence elements, accommodating large values.
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }

    // The queue will store the indices 'i' (1-based, as per problem statement) 
    // where an operation can potentially be performed.
    // An operation index 'i' corresponds to checking elements A_i, A_{i+1}, A_{i+2}
    // and modifying A_{i+1}.
    queue<int> q;
    
    // `is_in_queue` tracks if an operation index 'i' (1 to N-2) is currently in the queue.
    // We use a vector of size N for simplicity, mapping operation index `i` to `is_in_queue[i]`.
    // Indices 0 and N-1 will not be used for tracking operation indices.
    vector<bool> is_in_queue(N, false); 

    // Initial scan to find all eligible indices for the operation.
    // Iterate through possible operation indices i = 1 to N-2.
    for (int i = 1; i <= N - 2; ++i) {
        // Check the condition A_i < A_{i+1} and A_{i+1} > A_{i+2}.
        // Using 0-based indexing for vector A, this corresponds to checking A[i-1], A[i], A[i+1].
        if (A[i-1] < A[i] && A[i] > A[i+1]) {
            q.push(i); // Add eligible index to the queue
            is_in_queue[i] = true; // Mark index `i` as being in the queue
        }
    }

    // `count` stores the total number of operations performed. Use long long as it might exceed 32-bit integer limits.
    long long count = 0; 

    // Process the queue until it's empty (no more eligible operations).
    while (!q.empty()) {
        int i = q.front(); // Get the next operation index from the front of the queue.
        q.pop(); // Remove the index from the queue.
        is_in_queue[i] = false; // Mark index `i` as removed from the queue.

        // Sanity check if the index 'i' is within the valid range [1, N-2].
        // This should theoretically always be true if logic is correct, but good for safety.
        if (i < 1 || i > N - 2) continue;

        // Re-check eligibility before performing the operation. The state of A might have changed
        // due to operations performed on neighboring indices which could affect A[i-1] or A[i+1].
        // The condition still involves elements A[i-1], A[i], A[i+1].
        if (A[i-1] < A[i] && A[i] > A[i+1]) {
            // Perform the operation: modify A[i] (which corresponds to A_{i+1} in the problem statement).
            // The new value is min(A_i, A_{i+2}) - 1, which translates to min(A[i-1], A[i+1]) - 1 in 0-based indexing.
            A[i] = min(A[i-1], A[i+1]) - 1;
            count++; // Increment the operation count.

            // After modifying A[i], the eligibility of neighboring operations might change.
            // We need to check if operations at index i-1 or i+1 became eligible.
            
            // Check eligibility of operation index i-1.
            int prev_op_idx = i - 1;
            // Check if prev_op_idx is a valid operation index (1 <= prev_op_idx <= N-2).
            if (prev_op_idx >= 1) {
                 // The eligibility condition for operation index prev_op_idx involves elements
                 // A[prev_op_idx-1], A[prev_op_idx], A[prev_op_idx+1], which are A[i-2], A[i-1], A[i].
                 // Check if A[i-2] < A[i-1] and A[i-1] > A[i] holds (using the potentially new value of A[i]).
                 // Boundary check for A[i-2]: required i-2 >= 0, which means i >= 2. This is guaranteed since prev_op_idx >= 1 implies i >= 2.
                 if (A[i-2] < A[i-1] && A[i-1] > A[i]) { 
                     // If operation at prev_op_idx is now eligible and not already in the queue, add it.
                     if (!is_in_queue[prev_op_idx]) {
                       q.push(prev_op_idx);
                       is_in_queue[prev_op_idx] = true;
                    }
                }
            }

            // Check eligibility of operation index i+1.
            int next_op_idx = i + 1;
             // Check if next_op_idx is a valid operation index (1 <= next_op_idx <= N-2).
            if (next_op_idx <= N - 2) {
                 // The eligibility condition for operation index next_op_idx involves elements
                 // A[next_op_idx-1], A[next_op_idx], A[next_op_idx+1], which are A[i], A[i+1], A[i+2].
                 // Check if A[i] < A[i+1] and A[i+1] > A[i+2] holds (using the potentially new value of A[i]).
                 // Boundary check for A[i+2]: required i+2 < N. This is guaranteed since next_op_idx <= N-2 implies i <= N-3, so i+2 <= N-1 < N.
                 if (A[i] < A[i+1] && A[i+1] > A[i+2]) { 
                     // If operation at next_op_idx is now eligible and not already in the queue, add it.
                     if (!is_in_queue[next_op_idx]) {
                        q.push(next_op_idx);
                        is_in_queue[next_op_idx] = true;
                    }
                }
            }
        }
    }

    // Output the total number of operations performed.
    cout << count << endl;

    return 0;
}
0