結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:50:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,191 bytes
コンパイル時間 2,195 ms
コンパイル使用メモリ 198,316 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-15 22:52:07
合計ジャッジ時間 3,662 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

typedef long long ll;

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

struct Node {
    Line line;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(const Line& l) : line(l) {}
};

class LiChaoTree {
private:
    Node* root;
    const ll L;
    const ll R;

    void insert(Node*& node, ll l, ll r, Line new_line) {
        if (!node) {
            node = new Node(new_line);
            return;
        }
        ll m = (l + r) / 2;
        bool leftBetter = new_line.eval(l) > node->line.eval(l);
        bool midBetter = new_line.eval(m) > node->line.eval(m);
        bool rightBetter = new_line.eval(r) > node->line.eval(r);

        if (midBetter) {
            swap(node->line, new_line);
        }

        if (l == r) {
            return;
        }

        if (leftBetter != midBetter) {
            insert(node->left, l, m, new_line);
        } else if (rightBetter != midBetter) {
            insert(node->right, m+1, r, new_line);
        }
    }

    ll query(Node* node, ll l, ll r, ll x) {
        if (!node) return LLONG_MIN;
        ll curr = node->line.eval(x);
        ll m = (l + r) / 2;
        if (x <= m) {
            return max(curr, query(node->left, l, m, x));
        } else {
            return max(curr, query(node->right, m+1, r, x));
        }
    }

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

    void insert(const Line& line) {
        insert(root, L, R, line);
    }

    ll query(ll x) {
        return query(root, L, R, x);
    }
};

int main() {
    ios::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];
    }

    const ll MIN_X = -1e5;
    const ll MAX_X = 1e5;
    LiChaoTree tree(MIN_X, MAX_X);

    tree.insert({Q[0], 0});
    ll max_ans = LLONG_MIN;

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

    cout << max_ans << '\n';

    return 0;
}
0