結果
| 問題 |
No.3122 Median of Medians of Division
|
| コンテスト | |
| ユーザー |
 Naru820
|
| 提出日時 | 2025-05-21 16:22:40 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,201 bytes |
| コンパイル時間 | 2,115 ms |
| コンパイル使用メモリ | 117,616 KB |
| 実行使用メモリ | 60,160 KB |
| 最終ジャッジ日時 | 2025-05-21 16:22:56 |
| 合計ジャッジ時間 | 14,663 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 1 |
| other | TLE * 1 -- * 39 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
// Type definitions
using ll = long long;
// Structure for segment tree node
struct SegInfo {
bool first_val_is_one;
bool last_val_is_one;
int ones_count;
int transitions_1_to_0;
bool is_empty;
SegInfo() : first_val_is_one(false), last_val_is_one(false), ones_count(0), transitions_1_to_0(0), is_empty(true) {}
};
// Global segment tree and array (for simplicity in check function)
vector<ll> g_A_arr; // Global array A
vector<SegInfo> g_tree;
int g_N_seg; // Size of array for segment tree
// Merge function for segment tree nodes
SegInfo merge(const SegInfo& left, const SegInfo& right) {
if (left.is_empty) return right;
if (right.is_empty) return left;
SegInfo res;
res.is_empty = false;
res.ones_count = left.ones_count + right.ones_count;
res.first_val_is_one = left.first_val_is_one;
res.last_val_is_one = right.last_val_is_one;
res.transitions_1_to_0 = left.transitions_1_to_0 + right.transitions_1_to_0;
if (left.last_val_is_one && !right.first_val_is_one) {
res.transitions_1_to_0++;
}
return res;
}
// Build leaf node for segment tree
void build_leaf_seg_tree(int node_idx, int arr_idx, ll threshold_X) {
if (arr_idx >= g_A_arr.size()) { // Should not happen if arr_idx is valid
g_tree[node_idx].is_empty = true;
return;
}
g_tree[node_idx].is_empty = false;
bool is_one = (g_A_arr[arr_idx] >= threshold_X);
g_tree[node_idx].ones_count = is_one ? 1 : 0;
g_tree[node_idx].first_val_is_one = is_one;
g_tree[node_idx].last_val_is_one = is_one;
g_tree[node_idx].transitions_1_to_0 = 0;
}
// Build segment tree for a specific threshold X
void build_seg_tree(int node_idx, int l_arr, int r_arr, ll threshold_X) {
if (l_arr == r_arr) {
build_leaf_seg_tree(node_idx, l_arr, threshold_X);
} else {
int mid = l_arr + (r_arr - l_arr) / 2;
build_seg_tree(2 * node_idx, l_arr, mid, threshold_X);
build_seg_tree(2 * node_idx + 1, mid + 1, r_arr, threshold_X);
g_tree[node_idx] = merge(g_tree[2 * node_idx], g_tree[2 * node_idx + 1]);
}
}
// Query segment tree
SegInfo query_seg_tree(int node_idx, int l_arr, int r_arr, int q_l, int q_r) {
if (q_l <= l_arr && r_arr <= q_r) {
return g_tree[node_idx];
}
int mid = l_arr + (r_arr - l_arr) / 2;
SegInfo res_left, res_right;
if (q_l <= mid) {
res_left = query_seg_tree(2 * node_idx, l_arr, mid, q_l, q_r);
}
if (q_r > mid) {
res_right = query_seg_tree(2 * node_idx + 1, mid + 1, r_arr, q_l, q_r);
}
return merge(res_left, res_right);
}
// Check function for binary search
bool check(ll X_candidate, int l_query, int r_query, const vector<ll>& current_A_state) {
// Use g_A_arr for the check, by copying current_A_state to it
g_A_arr = current_A_state; // This copy is an O(N) operation.
// For faster parallel BS, g_A_arr itself would be updated.
// Here, for simple BS per query, this is fine conceptually.
if (g_N_seg > 0) build_seg_tree(1, 0, g_N_seg - 1, X_candidate); else g_tree[1].is_empty = true;
SegInfo range_info;
if (l_query <= r_query && g_N_seg > 0) {
range_info = query_seg_tree(1, 0, g_N_seg - 1, l_query, r_query);
} else {
return false; // Empty query range or empty main array cannot satisfy condition normally
}
if (range_info.is_empty) return false; // Should not happen if l_query <= r_query
int n1 = range_info.ones_count;
int n0_seg = 0;
if (!range_info.first_val_is_one) {
n0_seg = 1;
}
n0_seg += range_info.transitions_1_to_0;
return n1 > n0_seg;
}
struct Query {
int type;
int p1, p2;
ll val_x;
int original_idx_for_ans; // For type 2 queries to map back to answers array
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int Q_count;
cin >> g_N_seg >> Q_count;
vector<ll> initial_A(g_N_seg);
set<ll> distinct_coords_set;
distinct_coords_set.insert(0); // A potential smallest answer if all elements are negative (not in this problem)
// Or simply a baseline. The problem states 1 <= A_i.
// So, smallest possible answer is 1, or smallest element.
// A value smaller than all elements can be a sentinel for "no X works".
for (int i = 0; i < g_N_seg; ++i) {
cin >> initial_A[i];
distinct_coords_set.insert(initial_A[i]);
}
vector<Query> queries(Q_count);
vector<int> type2_original_indices;
for (int i = 0; i < Q_count; ++i) {
cin >> queries[i].type;
if (queries[i].type == 1) {
cin >> queries[i].p1 >> queries[i].val_x;
queries[i].p1--; // 0-indexed
distinct_coords_set.insert(queries[i].val_x);
} else {
cin >> queries[i].p1 >> queries[i].p2;
queries[i].p1--;
queries[i].p2--;
queries[i].original_idx_for_ans = type2_original_indices.size();
type2_original_indices.push_back(i);
}
}
vector<ll> distinct_coords(distinct_coords_set.begin(), distinct_coords_set.end());
if (distinct_coords.empty() || distinct_coords[0] > 1 && g_N_seg > 0) { // Ensure 0 or a value like 1 is present if needed
// Smallest A_i is 1. So smallest answer is 1 or an element.
// If all elements are large, 0 might be a valid output if no conditions met.
// The problem implies finding a value from the array elements or similar.
// If distinct_coords is empty (N=0), or if all are >0, and we need a "base" answer.
// For this problem, if N_1 > N_0_seg is never met, what's the answer?
// It implies we should output the smallest possible value that $A_i$ can take, or 0 if that's appropriate.
// The lowest value in `distinct_coords` (if sorted non-decreasingly) will be the first `current_best_X`.
}
vector<ll> answers(type2_original_indices.size());
g_tree.resize(4 * g_N_seg + 5); // Allocate segment tree memory
vector<ll> current_A_state = initial_A;
for(int q_idx = 0; q_idx < Q_count; ++q_idx) {
if (queries[q_idx].type == 1) {
current_A_state[queries[q_idx].p1] = queries[q_idx].val_x;
} else {
int l_query = queries[q_idx].p1;
int r_query = queries[q_idx].p2;
int ans_idx = queries[q_idx].original_idx_for_ans;
ll query_ans = 0; // Default answer if no X works (e.g., if all DV positive, this is smallest)
// The problem seems to imply result is one of A_i.
// The smallest value in distinct_coords (excluding a dummy 0 if added)
// could be initial query_ans. The problem asks for MAX value.
if (!distinct_coords.empty()) query_ans = distinct_coords[0];
int low_dc_idx = 0, high_dc_idx = distinct_coords.size() - 1;
// If N=0 or L>R, result might be 0 or handled by check.
// Smallest value in A_i is 1. So 0 is a safe default "no positive value works"
// However, the median calculation will always yield an element if partitions non-empty.
// So the "max possible value" will be one of the numbers present in A.
// Or 0 if no such partition scheme results in the condition.
// The problem implies result is one of the elements. Smallest element as default.
query_ans = 0; // Default to 0 if no X works, or use smallest from distinct_coords.
// Let's assume 0 is a valid output if condition never met for any X > 0.
while(low_dc_idx <= high_dc_idx) {
int mid_dc_idx = low_dc_idx + (high_dc_idx - low_dc_idx) / 2;
ll X_candidate = distinct_coords[mid_dc_idx];
if (X_candidate == 0 && g_N_seg > 0 && l_query <= r_query) { // Special handling if 0 is in DV and tested
// if all A_i are positive, X_candidate=0 means all A_i >= 0 -> all 1s.
// Generally, the problem values are positive.
// If we must pick a value from current A, then X_candidate shouldn't be 0 unless 0 is in A.
// Given 1 <= A_i, X_candidate won't be 0 unless we add it.
// We can assume distinct_coords[0] is the smallest actual value if we filter out dummy 0.
}
if (check(X_candidate, l_query, r_query, current_A_state)) {
query_ans = X_candidate;
low_dc_idx = mid_dc_idx + 1;
} else {
high_dc_idx = mid_dc_idx - 1;
}
}
answers[ans_idx] = query_ans;
}
}
for (size_t i = 0; i < answers.size(); ++i) {
cout << answers[i] << "\n";
}
return 0;
}