結果

問題 No.2458 Line Up Charged Balls
ユーザー gew1fw
提出日時 2025-06-12 14:54:48
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,948 bytes
コンパイル時間 3,051 ms
コンパイル使用メモリ 197,896 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-06-12 14:57:37
合計ジャッジ時間 5,787 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Line {
    ll m, b;
    Line(ll m, ll b) : m(m), b(b) {}
    ll eval(ll x) const {
        return m * x + b;
    }
};

class LiChaoTree {
    struct Node {
        Line line;
        Node* left;
        Node* right;
        Node(Line line) : line(line), left(nullptr), right(nullptr) {}
    };

    Node* root;
    const ll L, R;

public:
    LiChaoTree(ll l, ll r) : L(l), R(r), root(nullptr) {}

    void insert(Line new_line) {
        if (!root) {
            root = new Node(new_line);
            return;
        }

        Node* cur = root;
        ll l_current = L, r_current = R;

        while (true) {
            ll m = (l_current + r_current) >> 1;
            bool left_new = new_line.eval(l_current) > cur->line.eval(l_current);
            bool mid_new = new_line.eval(m) > cur->line.eval(m);
            bool right_new = new_line.eval(r_current) > cur->line.eval(r_current);

            if (mid_new) {
                swap(cur->line, new_line);
            }

            if (l_current == r_current) {
                break;
            }

            if (left_new != mid_new) {
                if (!cur->left) {
                    cur->left = new Node(new_line);
                    break;
                }
                cur = cur->left;
                r_current = m;
            } else if (right_new != mid_new) {
                if (!cur->right) {
                    cur->right = new Node(new_line);
                    break;
                }
                cur = cur->right;
                l_current = m + 1;
            } else {
                break;
            }
        }
    }

    ll query(ll x) {
        if (!root) return LLONG_MIN;

        ll res = LLONG_MIN;
        Node* cur = root;
        ll l = L, r = R;

        while (true) {
            res = max(res, cur->line.eval(x));
            ll m = (l + r) >> 1;
            if (x <= m) {
                if (cur->left) {
                    cur = cur->left;
                    r = m;
                } else {
                    break;
                }
            } else {
                if (cur->right) {
                    cur = cur->right;
                    l = m + 1;
                } else {
                    break;
                }
            }
        }

        return res;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ll> Q(N);
    for (int i = 0; i < N; ++i) {
        cin >> Q[i];
    }

    LiChaoTree tree(-1'000'000'000'000'000, 1'000'000'000'000'000);
    tree.insert(Line(Q[0], 0));

    ll max_ans = LLONG_MIN;

    for (int i = 1; i < N; ++i) {
        ll x = Q[i];
        ll current = tree.query(x);
        if (current > max_ans) {
            max_ans = current;
        }
        tree.insert(Line(Q[i], current));
    }

    cout << max_ans << endl;

    return 0;
}
0