結果
| 問題 |
No.2223 Merged Med
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:01:11 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 11,939 bytes |
| コンパイル時間 | 1,216 ms |
| コンパイル使用メモリ | 97,568 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:03:02 |
| 合計ジャッジ時間 | 9,945 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 10 TLE * 1 -- * 22 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <vector> // Ensure vector is included
// Use long long for potentially large prefix sums and infinity constant
using ValueType = long long;
// Define a large value for infinity, suitable for long long
const ValueType INF = 2e18;
// Structure for segment tree nodes
struct Node {
// Stores the maximum P_i value within the node's range of prefix sum values.
// Initialized to -INF to signify absence of value.
ValueType max_val = -INF;
};
// Global variables for segment tree implementation
std::vector<Node> tree; // The segment tree array
std::vector<ValueType> p_vals; // Stores unique prefix sum values for coordinate compression
std::map<ValueType, int> p_to_idx; // Maps a prefix sum value to its compressed index
/**
* @brief Builds coordinate compression map for prefix sum values.
* Sorts the unique prefix sum values and creates a mapping from each value to its rank (index).
* @param P Vector of prefix sums.
*/
void build_coord_map(const std::vector<ValueType>& P) {
p_vals.clear(); // Clear previous mapping data
p_to_idx.clear();
std::vector<ValueType> temp_p = P; // Create a temporary copy to sort
std::sort(temp_p.begin(), temp_p.end()); // Sort prefix sums to find unique values
p_vals.reserve(P.size()); // Optimize vector capacity
// Iterate through sorted values and add unique ones to p_vals
for (ValueType val : temp_p) {
if (p_vals.empty() || p_vals.back() != val) {
p_vals.push_back(val);
}
}
// Build the map from value to its index (rank)
for (int i = 0; i < p_vals.size(); ++i) {
p_to_idx[p_vals[i]] = i;
}
}
/**
* @brief Builds the segment tree structure recursively.
* Initializes all nodes with default value (-INF).
* @param node Current node index in the tree array.
* @param start Start index of the segment covered by this node.
* @param end End index of the segment covered by this node.
*/
void build(int node, int start, int end) {
if (start > end) return; // Base case: invalid range
tree[node] = {-INF}; // Initialize node's max_val
if (start == end) { // Base case: leaf node
return;
}
int mid = start + (end - start) / 2; // Calculate middle index
build(2 * node, start, mid); // Recursively build left child
build(2 * node + 1, mid + 1, end); // Recursively build right child
}
/**
* @brief Updates the segment tree at a specific index with a new value.
* The update sets the max_val at the leaf corresponding to `idx` to max(current_max, val).
* Propagates the update up the tree.
* @param node Current node index.
* @param start Start index of the node's range.
* @param end End index of the node's range.
* @param idx The compressed index to update.
* @param val The P_i value to potentially update with.
*/
void update(int node, int start, int end, int idx, ValueType val) {
// Check if index is outside the current node's range
if (start > end || idx < start || idx > end) return;
if (start == end) { // Reached the leaf node corresponding to the index
tree[node].max_val = std::max(tree[node].max_val, val); // Update max value
return;
}
int mid = start + (end - start) / 2; // Calculate middle index
// Recurse down to the appropriate child based on index
if (idx <= mid) {
update(2 * node, start, mid, idx, val);
} else {
update(2 * node + 1, mid + 1, end, idx, val);
}
// Update current node's max value based on its children's max values
tree[node].max_val = std::max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
}
/**
* @brief Queries the maximum value in the segment tree over a given range [L, R].
* The range refers to compressed indices.
* @param node Current node index.
* @param start Start index of the node's range.
* @param end End index of the node's range.
* @param L Start index of the query range.
* @param R End index of the query range.
* @return Maximum P_i value found in the query range, or -INF if none found.
*/
ValueType query(int node, int start, int end, int L, int R) {
// If query range is invalid or doesn't overlap with node's range
if (start > end || R < start || end < L || L > R) {
return -INF; // Return -INF indicating no value found
}
// If node's range is fully contained within query range
if (L <= start && end <= R) {
return tree[node].max_val; // Return this node's max value
}
int mid = start + (end - start) / 2; // Calculate middle index
// Recursively query left and right children and return the maximum of results
ValueType p1 = query(2 * node, start, mid, L, R);
ValueType p2 = query(2 * node + 1, mid + 1, end, L, R);
return std::max(p1, p2);
}
/**
* @brief Check function to determine if the beauty of subarray A[L_query..R_query] is <= V.
* Implements the logic derived using binary representation and prefix sums.
* Uses a segment tree over coordinate compressed prefix sum values for efficient queries.
* @param V The threshold value being tested.
* @param A The original array.
* @param L_query Start index of the query subarray (1-based).
* @param R_query End index of the query subarray (1-based).
* @return True if beauty <= V, False otherwise.
*/
bool check(int V, const std::vector<int>& A, int L_query, int R_query) {
int k = R_query - L_query + 1; // Length of the subarray
// Constraints state 1 <= L <= R <= N, so k >= 1. The k <= 0 case is not needed.
// Calculate prefix sums P based on threshold V
std::vector<ValueType> P(k + 1, 0); // P[0] = 0
ValueType current_S = 0;
for (int i = 0; i < k; ++i) {
// Convert A element to 1 if <= V, else -1
int val = (A[L_query + i - 1] <= V) ? 1 : -1; // Adjust to 0-based index for A
current_S += val; // Update the running sum
P[i + 1] = current_S; // Store prefix sum P[i+1]
}
ValueType S = P[k]; // The total sum S = P_k
// Perform coordinate compression on prefix sum values
build_coord_map(P);
int map_size = p_vals.size(); // Number of unique prefix sum values
// If map_size is 0, means P was empty or had only one identical value.
// Should not happen for k >= 1, as P will have at least P[0]=0 and P[1].
if (map_size == 0) {
return true; // Fallback, should not be reached under problem constraints.
}
// Initialize segment tree with appropriate size (4*map_size is safe)
tree.assign(4 * map_size + 4, {-INF});
build(1, 0, map_size - 1); // Build the tree structure
ValueType M = INF; // Initialize minimum value M = min f(T) to positive infinity
// Insert P_0 = 0 into the segment tree using its compressed index
update(1, 0, map_size - 1, p_to_idx[P[0]], P[0]);
// Iterate through j from 1 to k
for (int j = 1; j <= k; ++j) {
ValueType Pj = P[j]; // Current prefix sum P_j
// Case 1: Check subsegments where median <= V. Requires finding max P_i s.t. i < j and P_i <= P_j - 1.
int idx_le_Pj_minus_1 = -1;
// Find the largest compressed index `idx` such that `p_vals[idx] <= Pj - 1`.
auto it_le = std::upper_bound(p_vals.begin(), p_vals.end(), Pj - 1);
// If `it_le` is not the beginning, means there exists at least one element <= Pj - 1.
if (it_le != p_vals.begin()) {
idx_le_Pj_minus_1 = std::distance(p_vals.begin(), it_le) - 1;
}
ValueType max_Pi_le = -INF; // Max P_i found for Case 1
if (idx_le_Pj_minus_1 != -1) { // If a valid index range exists
// Query segment tree for max P_i in the range [0, idx_le_Pj_minus_1]
max_Pi_le = query(1, 0, map_size - 1, 0, idx_le_Pj_minus_1);
}
// If a valid P_i was found (value > -INF)
if (max_Pi_le > -INF) {
ValueType T = Pj - max_Pi_le; // Calculate difference T = P_j - P_i
if (T >= 1) { // Check condition for Case 1: T >= 1
ValueType current_f = T; // Calculate f(T) = T for T >= 1
M = std::min(M, current_f); // Update overall minimum M
}
}
// Case 2: Check subsegments where median > V. Requires finding max P_i s.t. i < j and P_i >= P_j.
int idx_ge_Pj = -1;
// Find the smallest compressed index `idx` such that `p_vals[idx] >= Pj`.
auto it_ge = std::lower_bound(p_vals.begin(), p_vals.end(), Pj);
// If `it_ge` is not the end iterator, means there exists at least one element >= Pj.
if (it_ge != p_vals.end()) {
idx_ge_Pj = std::distance(p_vals.begin(), it_ge);
}
ValueType max_Pi_ge = -INF; // Max P_i found for Case 2
if (idx_ge_Pj != -1 && idx_ge_Pj < map_size) { // Check if index is valid and within bounds
// Query segment tree for max P_i in range [idx_ge_Pj, map_size - 1]
max_Pi_ge = query(1, 0, map_size - 1, idx_ge_Pj, map_size - 1);
}
// If a valid P_i was found (value > -INF)
if (max_Pi_ge > -INF) {
ValueType T = Pj - max_Pi_ge; // Calculate difference T = P_j - P_i
if (T <= 0) { // Check condition for Case 2: T <= 0
ValueType current_f = T + 2; // Calculate f(T) = T + 2 for T <= 0
M = std::min(M, current_f); // Update overall minimum M
}
}
// Update segment tree with P_j's value `Pj` at its compressed index `p_to_idx[Pj]`.
// This makes Pj available as a potential P_i for future iterations j' > j.
if (p_to_idx.count(Pj)) { // Check if Pj is in the map (it should be)
update(1, 0, map_size - 1, p_to_idx[Pj], Pj);
} else {
// This branch indicates an error/bug since Pj must be in the map.
}
}
// After loop, M holds the minimum value of f(T) over all subsegments [l..r].
// If M is still INF, it means no valid subsegment was processed or updated M.
// This should not happen for k >= 1.
if (M == INF) {
// If k >= 1, M should be finite. This indicates an issue or unhandled edge case.
// Defaulting to true might be safer than possibly incorrect false.
return true;
}
// Final condition check: Total sum S must be >= Minimum value M found.
return S >= M;
}
int main() {
std::ios_base::sync_with_stdio(false); // Use faster I/O
std::cin.tie(NULL); // Untie cin and cout streams
int N, Q; // Read number of elements N and number of queries Q
std::cin >> N >> Q;
std::vector<int> A(N); // Declare vector A of size N
// Read elements of array A
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
}
// Process Q queries
for (int q = 0; q < Q; ++q) {
int L, R; // Read query range [L, R] (1-based indices)
std::cin >> L >> R;
// Binary search for the minimum possible median value (the "beauty")
// The beauty must be one of the values in A, so search range is [1, N].
int low = 1, high = N, ans = N + 1; // Initialize answer to a value outside range [1, N]
while(low <= high) { // Standard binary search loop
int mid = low + (high - low) / 2; // Calculate midpoint value to test
// Check if the beauty can be less than or equal to `mid`
if (check(mid, A, L, R)) {
ans = mid; // If yes, `mid` is a possible answer, try smaller values
high = mid - 1;
} else {
// If no, `mid` is too small, need a larger value
low = mid + 1;
}
}
// Output the minimum value found (the beauty)
std::cout << ans << "\n";
}
return 0; // Indicate successful execution
}