#1083857 (C++17) No.2458 Line Up Charged Balls

• 問題: 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;
}