A21668 蓝玛丽开公司 首发最快题解

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

const int MAX_T = 50000;
const int ROOT_NODE = 1;

struct line_t {
    double s;
    double p;

    line_t() : s(0.0), p(0.0) {}
    line_t(double start_val, double increment_val) : s(start_val), p(increment_val) {}

    double eval(int t) const {
        return s + static_cast<double>(t - 1) * p;
    }
};

std::vector<line_t> segment_tree;

void add_line_to_tree(line_t new_line, int node_idx, int l, int r);
double query_max_profit(int t, int node_idx, int l, int r);
void solve();

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

void solve() {
    int n;
    std::cin >> n;

    segment_tree.resize(4 * MAX_T + 4, line_t());

    for (int i = 0; i < n; ++i) {
        std::string command;
        std::cin >> command;
        if (command == "Project") {
            double s, p;
            std::cin >> s >> p;
            add_line_to_tree(line_t(s, p), ROOT_NODE, 1, MAX_T);
        } else {
            int t;
            std::cin >> t;
            double max_profit = query_max_profit(t, ROOT_NODE, 1, MAX_T);
            std::cout << static_cast<int>(max_profit / 100.0) << '\n';
        }
    }
}

void add_line_to_tree(line_t new_line, int node_idx, int l, int r) {
    if (segment_tree[node_idx].p == 0.0 && segment_tree[node_idx].s == 0.0) {
        segment_tree[node_idx] = new_line;
        return;
    }

    int mid = l + (r - l) / 2;
    
    bool new_is_better_at_mid = new_line.eval(mid) > segment_tree[node_idx].eval(mid);
    if (new_is_better_at_mid) {
        std::swap(segment_tree[node_idx], new_line);
    }

    if (l == r) {
        return;
    }

    bool new_is_better_at_l = new_line.eval(l) > segment_tree[node_idx].eval(l);
    if (new_is_better_at_l) {
        add_line_to_tree(new_line, 2 * node_idx, l, mid);
    } else {
        bool new_is_better_at_r = new_line.eval(r) > segment_tree[node_idx].eval(r);
        if (new_is_better_at_r) {
            add_line_to_tree(new_line, 2 * node_idx + 1, mid + 1, r);
        }
    }
}

double query_max_profit(int t, int node_idx, int l, int r) {
    double max_val = segment_tree[node_idx].eval(t);

    if (l == r) {
        return max_val;
    }

    int mid = l + (r - l) / 2;
    if (t <= mid) {
        max_val = std::max(max_val, query_max_profit(t, 2 * node_idx, l, mid));
    } else {
        max_val = std::max(max_val, query_max_profit(t, 2 * node_idx + 1, mid + 1, r));
    }

    return max_val;
}