#1083963 (C++17) No.1786 Maximum Suffix Median (Online)

• 問題: No.1786 Maximum Suffix Median (Online)
• ユーザー: qwewe
• 提出日時: 2025-05-14 13:11:09
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,734 bytes
• コンパイル時間: 697 ms
• コンパイル使用メモリ: 85,828 KB
• 実行使用メモリ: 12,452 KB
• 最終ジャッジ日時: 2025-05-14 13:13:14
• 合計ジャッジ時間: 5,169 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 5 TLE * 1 -- * 24

ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <set> // Use std::set to efficiently maintain distinct values

/**
 * @brief Checks if there exists a starting index j (1 <= j <= N_current) such that the median of the subarray A[j-1...N_current-1] is >= X.
 * The check is based on the property: median(S) >= X iff the number of elements in S that are >= X is greater than the number of elements < X.
 * This is equivalent to checking if sum(B_p) > 0 where B_p = 1 if A[p-1] >= X else -1, summed over p from j to N_current.
 * This condition can be further transformed using prefix sums S_k = sum(B_p for p=1..k).
 * The condition becomes: exists j in [1, N_current] such that S_{N_current} - S_{j-1} > 0.
 * This is equivalent to checking if S_{N_current} > min(S_0, S_1, ..., S_{N_current-1}).
 *
 * @param A The current array containing elements A_1, ..., A_{N_current}. Passed by const reference.
 * @param N_current The current length of the array A (which is `i` in the main loop).
 * @param X The value to check against.
 * @return True if there exists such a j, False otherwise.
 *
 * Time complexity: O(N_current) because it iterates through the first N_current elements of A.
 */
bool check(const std::vector<int>& A, int N_current, int X) {
    // current_S will store prefix sums S_k where S_k = sum_{p=0}^{k-1} B_p
    // B_p = 1 if A[p] >= X else -1. Note A is 0-indexed here.
    long long current_S = 0;
    // min_S_val stores the minimum value among S_0, S_1, ..., S_{N_current-1}.
    // S_0 is the empty prefix sum, which is 0.
    long long min_S_val = 0; 

    // Iterate through A[0...N_current-1]. k is 0-based index.
    for (int k = 0; k < N_current; ++k) { 
        // Determine B_{k+1} based on A[k] (the (k+1)-th element in 1-based indexing).
        int B_k_plus_1;
        if (A[k] >= X) {
             B_k_plus_1 = 1;
        } else {
             B_k_plus_1 = -1;
        }
        
        // Update current_S. After this update, current_S stores S_{k+1}.
        current_S += B_k_plus_1;
        
        // The check condition is S_{N_current} > min(S_0, S_1, ..., S_{N_current-1}).
        // We need to compute min_S_val = min(S_0, ..., S_{N_current-1}).
        // We update min_S_val based on prefix sums computed so far.
        // S_0 = 0. min_S_val is initialized to 0.
        // In iteration k, current_S becomes S_{k+1}.
        // We update min_S_val using values S_0 up to S_k.
        // The minimum required includes prefix sums up to index N_current-1.
        // So we update min_S_val with S_{k+1} if k+1 <= N_current-1, i.e., k < N_current - 1.
         if (k < N_current - 1) { 
           min_S_val = std::min(min_S_val, current_S);
        }
    }
    
    // After the loop, current_S holds the value of S_{N_current}.
    // We compare S_{N_current} with the minimum prefix sum found (min_S_val).
    return current_S > min_S_val;
}


int main() {
    // Fast IO operations
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N;
    std::cin >> N; // Read the total number of elements

    // Read the N potentially XORed values A'_i
    std::vector<int> A_prime(N);
    for (int k = 0; k < N; ++k) {
        std::cin >> A_prime[k];
    }

    // Vector A will store the actual sequence A_1, ..., A_N
    std::vector<int> A;
    A.reserve(N); // Reserve space to avoid reallocations
    int ans_prev = 0; // Stores ans_{i-1} for the online update

    // Use std::set to maintain distinct values seen so far efficiently.
    // Insertion takes O(log i) time on average at step i.
    std::set<int> distinct_A_set;

    // Process each element A_i from i=1 to N
    for (int i = 1; i <= N; ++i) { // i is 1-based index, represents current length of A
        int current_A_val;
        if (i == 1) {
            // First element A_1 is just A'_1
            current_A_val = A_prime[0];
        } else {
            // Subsequent elements A_i = A'_i XOR ans_{i-1}
            // Check potential integer overflow: A_i < 2^30, ans_{i-1} < 2^30.
            // XOR result is also < 2^30, fits within standard 32-bit signed int.
            current_A_val = A_prime[i - 1] ^ ans_prev;
        }
        // Add the computed A_i to the vector A
        A.push_back(current_A_val);
        // Add the new value to the set of distinct values encountered so far
        distinct_A_set.insert(current_A_val); 

        // Perform binary search on the distinct values encountered so far to find ans_i.
        // Copy the distinct values from set to vector for indexed access.
        // Copying takes O(i) time. Total time for this part across all steps is O(N^2).
        // Combined with O(i) check, total complexity is O(N^2 log N) or potentially O(N^3) if copy is dominant.
        // Using set allows O(N log N) for insertions total, but copy + check dominates.
        std::vector<int> distinct_A_vec(distinct_A_set.begin(), distinct_A_set.end());

        int best_val = 0; // The minimum possible median is 0 since A_i >= 0. Initialize answer to 0.
        
        // Binary search range is indices of the sorted distinct values vector.
        int low_idx = 0;
        int high_idx = distinct_A_vec.size() - 1;
        
        // The binary search finds the largest value X in distinct_A_vec such that check(A, i, X) is true.
        // This value X is the maximum possible median for suffixes ending at i.
        while (low_idx <= high_idx) {
            // Use midpoint calculation that avoids potential overflow for large indices
            int mid_idx = low_idx + (high_idx - low_idx) / 2; 
            int mid_val = distinct_A_vec[mid_idx]; // The candidate median value X
             
            // Pass the current length of A which is 'i'
            if (check(A, i, mid_val)) {
                 // If median >= mid_val is possible for some suffix, then mid_val is a potential answer.
                 // The true answer could be mid_val or something larger. Store mid_val as current best.
                 best_val = mid_val; 
                 // Try searching in the higher half (including mid_val itself is implicitly covered by best_val update)
                 low_idx = mid_idx + 1; 
            } else {
                 // If median >= mid_val is not possible for any suffix, mid_val is too high.
                 // The true answer must be smaller than mid_val.
                 // Search in the lower half.
                 high_idx = mid_idx - 1;
            }
        }
        
        // The value found in best_val is ans_i.
        ans_prev = best_val; // Update ans_prev for the next iteration
        std::cout << ans_prev << "\n"; // Print the result for step i
    }

    return 0;
}