結果
| 問題 |
No.1394 Changing Problems
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:59 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,344 bytes |
| コンパイル時間 | 758 ms |
| コンパイル使用メモリ | 86,668 KB |
| 実行使用メモリ | 32,972 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:02 |
| 合計ジャッジ時間 | 7,401 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 WA * 5 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits> // Required for numeric_limits
using namespace std;
// Define long long type for potentially large numbers
typedef long long ll;
// Use standard limits for min/max identity elements for segment trees
const ll LL_INF = numeric_limits<ll>::max();
// Use a sufficiently small value for negative infinity to avoid overflow issues
// Any value smaller than minimum possible A_i - (N-2) is okay.
const ll LL_NEG_INF = -4e18;
// Segment Tree node structure for Range Maximum Query
// Used to efficiently find T_max = max(0, max_i(A_i - (N-2)))
struct MaxSegTreeNode {
ll max_val = LL_NEG_INF; // Initialize with smallest possible value
};
vector<MaxSegTreeNode> max_seg_tree; // Segment tree array for T_max
vector<ll> A_for_Tmax; // Stores A_i - (N-2) values for leaf nodes
// Build the segment tree for T_max
void build_max_tree(int node, int start, int end) {
if (start == end) {
// Leaf node corresponds to an element A_i - (N-2)
if (start < A_for_Tmax.size()) {
max_seg_tree[node].max_val = A_for_Tmax[start];
}
} else {
int mid = start + (end - start) / 2;
build_max_tree(2 * node, start, mid);
build_max_tree(2 * node + 1, mid + 1, end);
// Internal node stores the maximum of its children
max_seg_tree[node].max_val = max(max_seg_tree[2 * node].max_val, max_seg_tree[2 * node + 1].max_val);
}
}
// Update a value in the segment tree for T_max
void update_max_tree(int node, int start, int end, int idx, ll val) {
// Check if index is within node's range
if (start > idx || end < idx) return;
if (start == end) {
// Update leaf node value
max_seg_tree[node].max_val = val;
} else {
int mid = start + (end - start) / 2;
// Recurse down to the correct child
if (idx <= mid) {
update_max_tree(2 * node, start, mid, idx, val);
} else {
update_max_tree(2 * node + 1, mid + 1, end, idx, val);
}
// Update internal node value based on children
max_seg_tree[node].max_val = max(max_seg_tree[2 * node].max_val, max_seg_tree[2 * node + 1].max_val);
}
}
// Query the maximum value in a range [l, r] in the segment tree for T_max
ll query_max_tree(int node, int start, int end, int l, int r) {
// Check for invalid range or range outside node's responsibility
if (r < start || end < l || l > r) {
return LL_NEG_INF; // Return identity element for max
}
// If node's range is fully contained within query range
if (l <= start && end <= r) {
return max_seg_tree[node].max_val;
}
// Recurse down to children
int mid = start + (end - start) / 2;
ll p1 = query_max_tree(2 * node, start, mid, l, r);
ll p2 = query_max_tree(2 * node + 1, mid + 1, end, l, r);
// Combine results from children
return max(p1, p2);
}
// Segment Tree node structure for Range Add and Range Minimum Query
// Used to efficiently find min M(r) = min (K * sum_p + f(r)) where f(r) = (K+1)r - K S_r
struct MinSegTreeNode {
ll min_val = LL_INF; // Initialize with largest possible value
ll lazy = 0; // Lazy tag for range updates
};
vector<MinSegTreeNode> min_seg_tree; // Segment tree array for f(r) values
vector<ll> initial_f_values; // Stores initial f(r) values for leaf nodes
// Push lazy updates down to children
void push(int node, int start, int end) {
if (min_seg_tree[node].lazy != 0 && start != end) { // Only push if not a leaf and lazy tag exists
// Apply lazy tag to children's min_val and lazy tag
min_seg_tree[2 * node].min_val += min_seg_tree[node].lazy;
min_seg_tree[2 * node].lazy += min_seg_tree[node].lazy;
min_seg_tree[2 * node + 1].min_val += min_seg_tree[node].lazy;
min_seg_tree[2 * node + 1].lazy += min_seg_tree[node].lazy;
// Clear current node's lazy tag
min_seg_tree[node].lazy = 0;
}
}
// Build the segment tree for f(r) values
void build_min_tree(int node, int start, int end) {
if (start == end) {
// Leaf node corresponds to an initial f(r) value
if (start < initial_f_values.size()) {
min_seg_tree[node].min_val = initial_f_values[start];
}
} else {
int mid = start + (end - start) / 2;
build_min_tree(2 * node, start, mid);
build_min_tree(2 * node + 1, mid + 1, end);
// Internal node stores the minimum of its children
min_seg_tree[node].min_val = min(min_seg_tree[2 * node].min_val, min_seg_tree[2 * node + 1].min_val);
}
}
// Update range [l, r] by adding delta
void update_min_tree(int node, int start, int end, int l, int r, ll delta) {
// Check for invalid range or range outside node's responsibility
if (r < start || end < l || l > r) {
return;
}
// If node's range is fully contained within update range
if (l <= start && end <= r) {
min_seg_tree[node].min_val += delta;
min_seg_tree[node].lazy += delta;
} else {
// Push lazy updates before recursing
push(node, start, end);
int mid = start + (end - start) / 2;
// Recurse down to children
update_min_tree(2 * node, start, mid, l, r, delta);
update_min_tree(2 * node + 1, mid + 1, end, l, r, delta);
// Update internal node value based on children
min_seg_tree[node].min_val = min(min_seg_tree[2 * node].min_val, min_seg_tree[2 * node + 1].min_val);
}
}
// Query the minimum value in a range [l, r] in the segment tree for f(r)
ll query_min_tree(int node, int start, int end, int l, int r) {
// Check for invalid range or range outside node's responsibility
if (r < start || end < l || l > r) {
return LL_INF; // Return identity element for min
}
// If node's range is fully contained within query range
if (l <= start && end <= r) {
return min_seg_tree[node].min_val;
}
// Push lazy updates before recursing
push(node, start, end);
int mid = start + (end - start) / 2;
// Recurse down to children
ll p1 = query_min_tree(2 * node, start, mid, l, r);
ll p2 = query_min_tree(2 * node + 1, mid + 1, end, l, r);
// Combine results from children
return min(p1, p2);
}
int main() {
// Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N;
cin >> N;
vector<ll> A(N); // Store the initial array A
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
// Handle the N=1 case separately as the main logic relies on K = N-1 > 0.
if (N == 1) {
int Q;
cin >> Q;
while (Q--) {
int i; // Query index (1-based)
ll x; // New value
cin >> i >> x;
A[i - 1] = x; // Update A
// For N=1, the minimum operations needed is max(0, A[0] - (N-2)) = max(0, A[0] - (-1)) = max(0, A[0] + 1)
cout << max(0LL, A[0] + 1) << "\n";
}
return 0;
}
// K = N-1 is used frequently in calculations
ll K = N - 1;
// N-2 is the target upper bound for A_i values
ll N_minus_2 = N - 2;
// Initialize segment tree for T_max calculation
A_for_Tmax.resize(N);
for(int i=0; i<N; ++i) {
// Store A_i - (N-2) for efficient T_max query later
A_for_Tmax[i] = A[i] - N_minus_2;
}
// Allocate memory for the segment tree (4*N is safe)
max_seg_tree.resize(4 * N);
// Build the tree based on initial values
build_max_tree(1, 0, N - 1);
// Initialize structures for M' calculation
ll current_sum_p = 0; // Stores sum of p_i = floor(A_i / K)
vector<ll> cnt(K, 0); // Stores counts of remainders b_i = A_i % K
vector<ll> p_vals(N); // Stores p_i for each A_i
vector<ll> b_vals(N); // Stores b_i for each A_i
// Calculate initial p_i, b_i, sum_p, and counts
for (int i = 0; i < N; ++i) {
// Since A[i] >= 0, standard C++ division and modulo work as floor division/modulo
p_vals[i] = A[i] / K;
b_vals[i] = A[i] % K;
current_sum_p += p_vals[i];
cnt[b_vals[i]]++;
}
// Calculate initial values of f(r) = (K+1)r - K S_r
initial_f_values.resize(K);
// S array stores prefix sums of cnt: S[r] = sum_{j=0}^{r-1} cnt[j]
vector<ll> S(K + 1, 0);
for (int r = 0; r < K; ++r) {
S[r+1] = S[r] + cnt[r];
}
for (int r = 0; r < K; ++r) {
// Calculate f(r) using the prefix sum S[r]
initial_f_values[r] = (K + 1) * (ll)r - K * S[r];
}
// Build segment tree for f(r) values
min_seg_tree.resize(4 * K);
// Only build if K > 0 (i.e., N >= 2)
if (K > 0) {
build_min_tree(1, 0, K - 1);
}
// Process Queries
int Q;
cin >> Q;
while (Q--) {
int i_idx; // Query index (1-based)
ll x; // New value for A[i_idx-1]
cin >> i_idx >> x;
i_idx--; // Adjust to 0-based index
// Update T_max segment tree with the new value x - (N-2)
update_max_tree(1, 0, N - 1, i_idx, x - N_minus_2);
// Query the overall maximum value from the T_max tree
ll current_max_A_minus_N2 = query_max_tree(1, 0, N - 1, 0, N - 1);
// T_max is max(0, overall maximum)
ll T_max = max(0LL, current_max_A_minus_N2);
// Update M' related structures based on the change in A[i_idx]
ll old_p = p_vals[i_idx]; // Old p value
ll old_b = b_vals[i_idx]; // Old remainder value
// Remove effect of old value
current_sum_p -= old_p;
cnt[old_b]--;
// Update the f(r) segment tree due to change in cnt[old_b]
if (K > 0) {
// Decrementing cnt[old_b] increases f(r) by K for all r > old_b
// Apply range update [old_b + 1, K - 1] with delta = K
if (old_b + 1 <= K - 1) { // Check if range is valid
update_min_tree(1, 0, K - 1, old_b + 1, K - 1, K);
}
}
// Calculate new p and b values for x
ll new_p = x / K;
ll new_b = x % K;
// Store new values
p_vals[i_idx] = new_p;
b_vals[i_idx] = new_b;
// Add effect of new value
current_sum_p += new_p;
cnt[new_b]++;
// Update the f(r) segment tree due to change in cnt[new_b]
if (K > 0) {
// Incrementing cnt[new_b] decreases f(r) by K for all r > new_b
// Apply range update [new_b + 1, K - 1] with delta = -K
if (new_b + 1 <= K - 1) { // Check if range is valid
update_min_tree(1, 0, K - 1, new_b + 1, K - 1, -K);
}
}
// Query the minimum f(r) value from the updated segment tree
ll min_f_r = 0; // Default for K=0 (N=1 case)
if (K > 0) { // If K>=1 (N>=2)
min_f_r = query_min_tree(1, 0, K - 1, 0, K - 1);
}
// Calculate M' using the current sum_p and min_f_r
// M' = min_r M(r) = min_r (K * sum_p + f(r)) = K * sum_p + min_r f(r)
ll M_prime = K * current_sum_p + min_f_r;
// The final answer is the maximum of T_max and M'
cout << max(T_max, M_prime) << "\n";
}
return 0;
}