#1172428 (C++23) No.2465 Dilated Water Simulation

• 問題: No.2465 Dilated Water Simulation
• ユーザー: butsurizuki
• 提出日時: 2026-07-22 02:36:30
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 122 ms / 2,000 ms
• コード長: 10,667 bytes
• コンパイル時間: 2,366 ms
• コンパイル使用メモリ: 349,812 KB
• 実行使用メモリ: 43,904 KB
• 最終ジャッジ日時: 2026-07-22 02:36:37
• 合計ジャッジ時間: 7,064 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 25

ソースコード

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

using i64 = long long;
using i128 = __int128_t;

static const i128 INF128 = (i128(1) << 120);

struct Line {
    i64 slope = 0;
    i128 intercept = INF128;

    i128 eval(i64 x) const {
        return (i128)slope * x + intercept;
    }
};

// 直線追加を rollback できる Li Chao Tree
struct RollbackLiChao {
    int x_left;
    int x_right;

    const vector<Line>* lines;

    // 各ノードに格納されている直線番号
    vector<int> tree;

    // (変更したノード, 変更前の直線番号)
    vector<pair<int, int>> history;

    RollbackLiChao(
        int x_left_,
        int x_right_,
        const vector<Line>* lines_,
        int reserve_lines = 0
    )
        : x_left(x_left_),
          x_right(x_right_),
          lines(lines_),
          tree(4 * max(1, x_right_ - x_left_ + 1) + 16, -1) {

        if (reserve_lines > 0) {
            history.reserve((size_t)reserve_lines * 20);
        }
    }

    size_t snapshot() const {
        return history.size();
    }

    void rollback(size_t snapshot_size) {
        while (history.size() > snapshot_size) {
            auto [node, old_line] = history.back();
            history.pop_back();
            tree[node] = old_line;
        }
    }

    void assign_node(int node, int line_id) {
        history.push_back({node, tree[node]});
        tree[node] = line_id;
    }

    void add_line_rec(int node, int left, int right, int line_id) {
        if (tree[node] == -1) {
            assign_node(node, line_id);
            return;
        }

        int middle = (left + right) / 2;
        int current_id = tree[node];

        bool better_at_left =
            (*lines)[line_id].eval(left)
            < (*lines)[current_id].eval(left);

        bool better_at_middle =
            (*lines)[line_id].eval(middle)
            < (*lines)[current_id].eval(middle);

        if (better_at_middle) {
            assign_node(node, line_id);
            line_id = current_id;
        }

        if (left == right) {
            return;
        }

        if (better_at_left != better_at_middle) {
            add_line_rec(
                node * 2,
                left,
                middle,
                line_id
            );
        } else {
            add_line_rec(
                node * 2 + 1,
                middle + 1,
                right,
                line_id
            );
        }
    }

    void add_line(int line_id) {
        add_line_rec(
            1,
            x_left,
            x_right,
            line_id
        );
    }

    i128 query_rec(
        int node,
        int left,
        int right,
        int x
    ) const {
        i128 answer = INF128;

        if (tree[node] != -1) {
            answer = (*lines)[tree[node]].eval(x);
        }

        if (left == right) {
            return answer;
        }

        int middle = (left + right) / 2;

        if (x <= middle) {
            answer = min(
                answer,
                query_rec(
                    node * 2,
                    left,
                    middle,
                    x
                )
            );
        } else {
            answer = min(
                answer,
                query_rec(
                    node * 2 + 1,
                    middle + 1,
                    right,
                    x
                )
            );
        }

        return answer;
    }

    i128 query(int x) const {
        return query_rec(
            1,
            x_left,
            x_right,
            x
        );
    }
};

// LIFO の push/pop と直線最小値を管理するスタック
struct HullStack {
    RollbackLiChao hull;

    vector<int> line_ids;
    vector<size_t> snapshots;

    HullStack(
        int x_left,
        int x_right,
        const vector<Line>* lines,
        int reserve_lines = 0
    )
        : hull(
            x_left,
            x_right,
            lines,
            reserve_lines
        ) {

        if (reserve_lines > 0) {
            line_ids.reserve(reserve_lines);
            snapshots.reserve(reserve_lines);
        }
    }

    bool empty() const {
        return line_ids.empty();
    }

    void push(int line_id) {
        snapshots.push_back(hull.snapshot());
        line_ids.push_back(line_id);
        hull.add_line(line_id);
    }

    int pop() {
        int line_id = line_ids.back();

        hull.rollback(snapshots.back());

        line_ids.pop_back();
        snapshots.pop_back();

        return line_id;
    }

    i128 query(int x) const {
        if (empty()) {
            return INF128;
        }
        return hull.query(x);
    }
};

// 二つのスタックでキューを作る
struct HullQueue {
    HullStack input_stack;
    HullStack output_stack;

    HullQueue(
        int x_left,
        int x_right,
        const vector<Line>* lines,
        int reserve_lines = 0
    )
        : input_stack(
            x_left,
            x_right,
            lines,
            reserve_lines
        ),
          output_stack(
            x_left,
            x_right,
            lines,
            reserve_lines
        ) {}

    void push_back(int line_id) {
        input_stack.push(line_id);
    }

    void move_to_output() {
        if (!output_stack.empty()) {
            return;
        }

        while (!input_stack.empty()) {
            output_stack.push(input_stack.pop());
        }
    }

    void pop_front() {
        move_to_output();
        output_stack.pop();
    }

    i128 query(int x) const {
        return min(
            input_stack.query(x),
            output_stack.query(x)
        );
    }
};

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

    int L;
    cin >> L;

    vector<i64> capacity(L);
    for (i64& value : capacity) {
        cin >> value;
    }

    i64 N;
    cin >> N;

    const i64 full_cycles = N / L;
    const int remainder = (int)(N % L);

    const i64 minimum_capacity =
        *min_element(
            capacity.begin(),
            capacity.end()
        );

    vector<i64> reduced_capacity(L);

    for (int i = 0; i < L; ++i) {
        reduced_capacity[i] =
            capacity[i] - minimum_capacity;
    }

    vector<i64> answer(L, 0);

    const i64 total_reduced_water =
        reduced_capacity[0];

    // 一周も行わない場合、または残りの水が存在しない場合
    if (full_cycles == 0 || total_reduced_water == 0) {
        answer[0] = total_reduced_water;
    } else {
        // 最初の容量 0 の容器
        // 関係する容器は 0,...,M-1
        int M = 1;

        while (
            M < L &&
            reduced_capacity[M] > 0
        ) {
            ++M;
        }

        if (M == 1) {
            // 直後が容量 0 なので残りの水は動かない
            answer[0] = total_reduced_water;
        } else {
            vector<i128> prefix_sum(M + 1, 0);

            for (int i = 0; i < M; ++i) {
                prefix_sum[i + 1] =
                    prefix_sum[i]
                    + reduced_capacity[i];
            }

            // r=1,...,M-2 に対応する直線
            vector<Line> lines(M);

            for (int r = 1; r <= M - 2; ++r) {
                lines[r].slope =
                    reduced_capacity[r];

                lines[r].intercept =
                    prefix_sum[r]
                    + (
                        (i128)full_cycles - r
                    ) * reduced_capacity[r];
            }

            const int max_x = max(1, M - 2);

            HullQueue queue(
                1,
                max_x,
                &lines,
                M
            );

            // l=1 のとき有効な r は
            // 1,...,min(M-2,K)
            i64 initial_right =
                min<i64>(
                    M - 2,
                    full_cycles
                );

            for (
                int r = 1;
                r <= initial_right;
                ++r
            ) {
                queue.push_back(r);
            }

            // F[i] = 辺 i -> i+1 の累積移動量
            vector<i64> cumulative_flow(M - 1, 0);

            // W による上限
            i128 prefix_minimum =
                total_reduced_water;

            for (int l = 1; l <= M - 1; ++l) {
                i128 best_cost = INF128;

                // 終点 M-1 に到達しない候補
                if (l <= M - 2) {
                    best_cost =
                        queue.query(l)
                        - prefix_sum[l];
                }

                // 終点 M-1 へ直接到達する候補
                if (
                    (i64)M - l
                    <= full_cycles
                ) {
                    best_cost = min(
                        best_cost,
                        prefix_sum[M]
                        - prefix_sum[l]
                    );
                }

                prefix_minimum = min(
                    prefix_minimum,
                    best_cost
                );

                // prefix_minimum <= W <= 1e9
                cumulative_flow[l - 1] =
                    (i64)prefix_minimum;

                if (l <= M - 2) {
                    // 次の l では r=l が範囲外になる
                    queue.pop_front();

                    // 新しく r=l+K が範囲に入る
                    i64 new_r =
                        (i64)l + full_cycles;

                    if (new_r <= M - 2) {
                        queue.push_back(
                            (int)new_r
                        );
                    }
                }
            }

            // 累積移動量から各容器の水量を復元
            answer[0] =
                total_reduced_water
                - cumulative_flow[0];

            for (int i = 1; i <= M - 2; ++i) {
                answer[i] =
                    cumulative_flow[i - 1]
                    - cumulative_flow[i];
            }

            answer[M - 1] =
                cumulative_flow[M - 2];
        }
    }

    // 共通部分 m は完全な周の境界では容器 0 にある
    answer[0] += minimum_capacity;

    // 残り N mod L 回を直接シミュレーション
    for (int i = 0; i < remainder; ++i) {
        i64 moved = min(
            answer[i],
            capacity[i + 1] - answer[i + 1]
        );

        answer[i] -= moved;
        answer[i + 1] += moved;
    }

    for (int i = 0; i < L; ++i) {
        if (i != 0) {
            cout << ' ';
        }
        cout << answer[i];
    }

    cout << '\n';
    return 0;
}