結果
| 問題 |
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;
}