結果
| 問題 | No.2458 Line Up Charged Balls |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:05:18 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 61 ms / 2,000 ms |
| コード長 | 8,732 bytes |
| コンパイル時間 | 829 ms |
| コンパイル使用メモリ | 76,940 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:06 |
| 合計ジャッジ時間 | 2,968 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Define long long type for potentially large energy values
typedef long long ll;
// Use a large negative value to represent negative infinity.
// This value should be smaller than any possible valid energy calculation.
// Minimum possible energy can be roughly -(N-1) * (10^5)^2 ~ -3e5 * 1e10 = -3e15.
// LLONG_MIN is about -9e18. -5e18 should be safe.
const ll INF = -5e18;
// Structure to represent a line y = mx + c
struct Line {
ll m, c; // slope m, y-intercept c
// Default constructor represents an "invalid" line equivalent to negative infinity.
// This is used for nodes in the Li Chao Tree that don't yet store a valid line.
Line() : m(0), c(INF) {}
Line(ll _m, ll _c) : m(_m), c(_c) {}
// Evaluate the line at a given point x
ll eval(ll x) const {
// Check if this line is the default "invalid" line.
if (c == INF && m == 0) return INF;
// Calculate the value y = mx + c.
// Check potential overflow? With ll for m, c, x, the intermediate m*x can reach 10^10.
// Max c can reach ~3e15. Sum is within ll range (~9e18). Standard ll arithmetic is fine.
return m * x + c;
}
};
// Define the coordinate range bounds for charges Q_i as long long
const ll COORD_MIN_LL = -100000LL;
const ll COORD_MAX_LL = 100000LL;
// Node structure for the dynamic Li Chao Tree
struct Node {
Line line; // The line stored in this node, representing the best line over some part of the range
Node *left = nullptr; // Pointer to the left child node
Node *right = nullptr; // Pointer to the right child node
Node() : line() {} // Initialize with a default invalid line
// Destructor to prevent memory leaks by recursively deleting child nodes
~Node() {
delete left;
delete right;
}
};
// Function to insert a line into the Li Chao Tree
// Node*& node: reference to the pointer to the current node (allows creating node if null)
// ll L, R: the coordinate range [L, R] covered by the current node
void insert_line(Line new_line, Node*& node, ll L, ll R) {
// If the current node doesn't exist, create it.
if (!node) node = new Node();
// Evaluate the new line and the line currently stored in the node at the boundaries L and R.
ll eval_L_new = new_line.eval(L);
ll eval_L_node = node->line.eval(L);
ll eval_R_new = new_line.eval(R);
ll eval_R_node = node->line.eval(R);
// Strategy: Ensure node->line is always the line that is better or equal at the left boundary L.
// If new_line is better at L, swap it with node->line.
if (eval_L_new > eval_L_node) {
swap(new_line, node->line);
// After swapping, update the evaluated values for consistency in subsequent comparisons.
swap(eval_L_new, eval_L_node);
swap(eval_R_new, eval_R_node);
}
// After potentially swapping, check if new_line is completely dominated by node->line within [L, R].
// Since we ensured node->line is >= new_line at L, we only need to check at R.
if (eval_R_new <= eval_R_node) {
return; // new_line is dominated, no need to proceed further down this path.
}
// If the current range [L, R] represents a single point, we've updated the line if needed. Base case.
if (L == R) return;
// Calculate the midpoint M for splitting the range. Use safe calculation to avoid overflow.
ll M = L + (R - L) / 2;
// Determine which half of the range [L, R] the new_line might be better in.
// Compare the lines at the midpoint M.
if (new_line.eval(M) > node->line.eval(M)) {
// If new_line is better at M, it means the intersection point is in the left half [L, M].
// The line currently worse at M (new_line after swap) might still be the best in some part of [L, M].
swap(node->line, new_line); // Swap lines again: now node->line is the one better at M.
// Recursively insert the line that is now worse at M (originally node->line before this swap) into the left child.
insert_line(new_line, node->left, L, M);
} else {
// If node->line is better or equal at M, the intersection point (if any) must be in the right half [M+1, R].
// Recursively insert new_line (which is worse at M) into the right child.
insert_line(new_line, node->right, M + 1, R);
}
}
// Function to query the Li Chao Tree for the maximum value at point x
// Node* node: pointer to the current node
// ll L, R: the coordinate range [L, R] covered by the current node
ll query_tree(ll x, Node* node, ll L, ll R) {
// If the node doesn't exist, it means no line covers this part of the range effectively. Return INF.
if (!node) return INF;
// Get the value from the line stored at the current node.
ll max_val = node->line.eval(x);
// If this is a leaf node (range is a single point), return the value from its line.
if (L == R) return max_val;
// Calculate the midpoint M.
ll M = L + (R - L) / 2;
ll child_val = INF; // Initialize the result from child query to INF.
// Determine which child node to recurse into based on x's position relative to M.
if (x <= M) {
// If x is in the left half, query the left child (if it exists).
if (node->left)
child_val = query_tree(x, node->left, L, M);
} else {
// If x is in the right half, query the right child (if it exists).
if (node->right)
child_val = query_tree(x, node->right, M + 1, R);
}
// The maximum value at x is the maximum of the value from the current node's line
// and the maximum value found in the relevant child's subtree.
return max(max_val, child_val);
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of balls
cin >> N;
vector<ll> Q(N + 1); // Use 1-based indexing for charges Q[1]..Q[N]
for (int i = 1; i <= N; ++i) {
cin >> Q[i];
}
Node* root = nullptr; // Initialize the root of the dynamic Li Chao Tree as null
// dp[i] would store the maximum energy of a subsequence ending at index i.
// We only need the overall maximum energy, so we can just track `max_energy`.
ll max_energy = INF; // Initialize overall maximum energy found so far to negative infinity.
// Initialization step based on the first ball (index 1).
// Conceptually, dp[1] = INF because a sequence must have length >= 2.
// V_j = max(0, dp[j]). For j=1, V_1 = max(0, INF) = 0.
ll V1 = 0;
// The first line to insert corresponds to using ball 1 as the first element of a pair.
// The line form is y = Q_j * x + V_j. For j=1, it's y = Q[1]*x + V1 = Q[1]*x + 0.
Line f1(Q[1], V1);
// Insert this first line into the Li Chao Tree over the full coordinate range.
insert_line(f1, root, COORD_MIN_LL, COORD_MAX_LL);
// Iterate through balls from index 2 to N.
for (int i = 2; i <= N; ++i) {
// The query point x is the charge of the current ball Q[i].
ll query_x = Q[i];
// Query the tree to find the maximum value of V_j + Q_j * Q_i over all j < i.
// This gives the maximum possible energy for a sequence ending at ball i.
ll current_max = query_tree(query_x, root, COORD_MIN_LL, COORD_MAX_LL);
// This `current_max` is the value of dp[i].
ll current_dp_val = INF; // Default to INF if query returns INF.
if (current_max != INF) {
current_dp_val = current_max;
// Update the overall maximum energy found so far if dp[i] is greater.
if (current_dp_val > max_energy) {
max_energy = current_dp_val;
}
}
// Calculate V_i = max(0, dp[i]) for inserting the next line.
// If current_dp_val is INF (our large negative number), max(0, current_dp_val) correctly yields 0.
ll Vi = max(0LL, current_dp_val);
// Create the line corresponding to ball i: y = Q[i]*x + Vi
Line fi(Q[i], Vi);
// Insert this line into the Li Chao Tree for future queries.
insert_line(fi, root, COORD_MIN_LL, COORD_MAX_LL);
}
// Since N >= 3, the loop runs at least once (for i=2).
// dp[2] = Q[1]*Q[2] will be computed.
// max_energy will be updated to at least dp[2].
// Thus, max_energy should always hold a finite value (possibly negative or zero).
cout << max_energy << endl;
// Clean up the dynamically allocated memory for the Li Chao Tree nodes.
delete root;
return 0;
}